0位运算中等 LeetCode89. 格雷编码

89. 格雷编码

描述

n 位格雷码序列 是一个由 2n 个整数组成的序列,其中:
每个整数都在范围 [0, 2n - 1] 内(含 0 和 2n - 1)
第一个整数是 0
一个整数在序列中出现 不超过一次
每对 相邻 整数的二进制表示 恰好一位不同 ,且
第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n ,返回任一有效的 n 位格雷码序列 。

分析

找规律G(n)的格雷码是在G(n-1)的基础上反转G(n-1)的格雷码且加上(1<<n-1)得来的。
比如G(1)的格雷码是00、01,G(2)的格雷码是00、01、11、10
G(2)的格雷码可以看成由00、01加上(01 | 1 << 1)、(00 | 1 << 1)得来,也就是G(2)的格雷码等于G(1)的格雷码加上反转后的G(1)的格雷码且给每个反转的G(1)格雷码加上2的1次方。
要求更高的格雷码可以从2开始推算得到。

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> ans = new ArrayList<>();
        ans.add(0);
        if(n == 0) return ans;
        ans.add(1);
        if(n == 1) return ans;

        int index = 1;
        while(index < n){
            int size = ans.size()-1;
            for(int i = size; i >= 0; i--){
                ans.add(ans.get(i) | 1 << index );
            }
            index++;
        }
        return ans;
    }
}
上一篇:【报告分享】2021民宿行业数据报告-云掌柜(附下载)


下一篇:洛谷试炼场 DAY 01