89. 格雷编码
程序员文章站
2022-07-15 11:59:05
...
问题
格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n,打印其格雷编码序列。格雷编码序列必须以 0 开头。
例子
思路
-
方法1
镜像反射法
n阶格雷码集合为G(n),G(n+1)格雷码为:
将G(n)每个元素二进制形式前面添加0,得到G’(n)【和G(n)一样】
将G(n)倒序为R(n),在R(n)每个元素二进制形式前面添加1,得到R’(n)
G(n+1)=G’(n)+R’(n)=G(n)+R’(n) -
方法2
代码
//方法1
class Solution {
public List<Integer> grayCode(int n) {
List<Integer> list = new ArrayList<>();
list.add(0);
for(int i=1; i<=n; i++) {
for(int j=list.size()-1; j>=0; j--) {
int head = 1<<(i-1);
list.add(head+list.get(j));
}
}
return list;
}
}
//方法2
for(int i=0; i<1<<n; i++) {
list.add(i^(i>>1));
}
return list;