Posted on 2013-05-20 21:09
小明 閱讀(2582)
評(píng)論(0) 編輯 收藏 所屬分類:
數(shù)據(jù)結(jié)構(gòu)和算法
分析：
格雷碼的序列中應(yīng)包含2^n個(gè)數(shù)。這個(gè)問(wèn)題初看起來(lái)不容易，我們要想出一個(gè)生成方法。
對(duì)于n=2,序列是：
00，01，11，10
那對(duì)于n=3,如何利用n=2的序列呢？一個(gè)方法是，先在n=2的四個(gè)序列前加0（這其實(shí)是保持不變），然后再考慮把最高位變成1，只需要把方向反過(guò)來(lái)就可以了
000，001，011，010
100，101，111，110－> 110,111,101,100
把這兩行合起來(lái)就可以得到新的序列。
想通了，寫(xiě)代碼就很容易了。
public class Solution {
public ArrayList<Integer> grayCode(int n) {
ArrayList<Integer> result = new ArrayList<Integer>();
result.add(0);
if(n>0){
result.add(1);
}
int mask = 1;
for(int i=2;i<=n;++i){
mask *= 2;
for(int j=result.size()-1;j>=0;--j){
int v = result.get(j).intValue();
v |= mask;
result.add(v);
}
}
return result;
}
}