欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

89. 格雷编码

程序员文章站 2022-07-15 11:59:05
...

问题

格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n,打印其格雷编码序列。格雷编码序列必须以 0 开头。

例子
89. 格雷编码

思路

  • 方法1
    89. 格雷编码

    镜像反射法
    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
    89. 格雷编码

代码

//方法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;