Posted on 2013-05-20 21:09
小明 閱讀(2587)
評論(0) 編輯 收藏 所屬分類:
數據結構和算法
分析：
格雷碼的序列中應包含2^n個數。這個問題初看起來不容易，我們要想出一個生成方法。
對于n=2,序列是：
00，01，11，10
那對于n=3,如何利用n=2的序列呢？一個方法是，先在n=2的四個序列前加0（這其實是保持不變），然后再考慮把最高位變成1，只需要把方向反過來就可以了
000，001，011，010
100，101，111，110－> 110,111,101,100
把這兩行合起來就可以得到新的序列。
想通了，寫代碼就很容易了。
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;
}
}