Posted on 2013-05-20 21:09
小明 阅读(2568)
评论(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;
}
}