lintcode 411. 格雷编码

本是古典何须时尚 2023-07-24 11:44 10阅读 0赞

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

给定一个非负整数 n ，表示该代码中所有二进制的总数，请找出其格雷编码顺序。一个格雷编码顺序必须以 0 开始，并覆盖所有的 2n 个整数。

样例
    样例 1:
    
    输入: 1
    输出: [0, 1]
    样例 2:
    
    输入: 2
    输出: [0, 1, 3, 2]
    解释: 
      0 - 00
      1 - 01
      3 - 11
      2 - 10
    挑战
    O(2n) 时间复杂度。
    
    注意事项
    对于给定的 n，其格雷编码顺序并不唯一。
    
    当n = 2时，根据上面的定义，[0,1,3,2] 和 [0,2,3,1] 都是有效的格雷编码顺序。

假设原始的值从0开始，格雷码产生的规律是：第一步，改变最右边的位元值；第二步，改变右起第一个为1的位元的左边位元；第三步，第四步重复第一步和第二步，直到所有的格雷码产生完毕（换句话说，已经走了(2^n) - 1 步）。

用一个例子来说明：  
假设产生3位元的格雷码，原始值位 000  
第一步：改变最右边的位元值： 001  
第二步：改变右起第一个为1的位元的左边位元： 011  
第三步：改变最右边的位元值： 010  
第四步：改变右起第一个为1的位元的左边位元： 110  
第五步：改变最右边的位元值： 111  
第六步：改变右起第一个为1的位元的左边位元： 101  
第七步：改变最右边的位元值： 100

如果按照这个规则来生成格雷码，是没有问题的，但是这样做太复杂了。如果仔细观察格雷码的结构，我们会有以下发现：  
1、除了最高位（左边第一位），格雷码的位元完全上下对称（看下面列表）。比如第一个格雷码与最后一个格雷码对称（除了第一位），第二个格雷码与倒数第二个对称，以此类推。  
2、最小的重复单元是 0 , 1。

000  
001  
011  
010  
110  
111  
101  
100

所以，在实现的时候，我们完全可以利用递归，在每一层前面加上0或者1，然后就可以列出所有的格雷码。  
比如：  
第一步：产生 0, 1 两个字符串。  
第二步：在第一步的基础上，每一个字符串都加上0和1，但是每次只能加一个，所以得做两次。这样就变成了 00,01,11,10 （注意对称）。  
第三步：在第二步的基础上，再给每个字符串都加上0和1，同样，每次只能加一个，这样就变成了 000,001,011,010,110,111,101,100。  
好了，这样就把3位元格雷码生成好了。  
如果要生成4位元格雷码，我们只需要在3位元格雷码上再加一层0,1就可以了： 0000,0001,0011,0010,0110,0111,0101,0100,1100,1101,1110,1010,0111,1001,1000.

class Solution {
        
    public:
        /**
         * @param n: a number
         * @return: Gray code
         */
        vector<int> grayCode(int n) {
        
            // write your code here
            vector<int> res;
            if(n==0)
            {
        
                res.push_back(0);
                return res;
            }
            if(n==1)
            {
        
                res.push_back(0);
                res.push_back(1);
                return res;
            }
            vector<int> tmp=grayCode(n-1);//递归从第一级开始
            res=tmp;//继承加上前缀0部分
            int add=pow(2,n-1);//加上1部分的值
            for (int i = tmp.size()-1; i >=0 ; i--) {
        
                res.push_back(tmp[i]+add);//根据对称性加1前缀的值
            }
            return res;
        }
    };

参考博文：https://blog.csdn.net/beiyeqingteng/article/details/7044471