Leetcode: Gray Code

古城微笑少年丶 2022-08-07 12:56 50阅读 0赞

题目：  
The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return \[0,1,3,2\]. Its gray code sequence is:

00 - 0
    01 - 1
    11 - 3
    10 - 2

Note:  
For a given n, a gray code sequence is not uniquely defined.

For example, \[0,2,3,1\] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

Gray Code：  
在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code）。格雷码当初是为了通信，现在则常用于模拟－数字转换和位置－数字转换中。

Gray Code转换方法：  
**递归生成码表**  
这种方法基于格雷码是反射码的事实，利用递归的如下规则来构造：

1. 1位格雷码有两个码字 
    
     2. n位格雷码中的前2(n-1)个码字等于n-1位格雷码的码字，按顺序书写，加前缀0 
    
     3. (n+1)位格雷码中的后2(n-1)个码字等于n-1位格雷码的码字，按逆序书写，加前缀1

C++参考代码（用时7ms）：

class Solution
    {
    public:
        vector<int> grayCode(int n)
        {
            vector<int> codes;
            codes.push_back(0);
            for (int i = 0; i < n; ++i)
            {
                int one = 1 << i;//最高位的数字1
                int size = int(codes.size());
                //这个循环要倒序哦
                for (int j = size - 1; j >= 0; --j)
                {
                    codes.push_back(one + codes[j]);
                }
            }
            return codes;
        }
    };

**异或转换**  
二进制码->格雷码（编码）：

1. 从0到2n-1编号 
    
     2. 从最右边一位起，依次将每一位与左边一位异或（XOR），作为对应格雷码该位的值，最左边一位不变（相当于左边是0）；

格雷码->二进制码（解码）：  
从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）。

C++代码（用时9ms）：

class Solution
    {
    public:
        vector<int> grayCode(int n)
        {
            vector<int> codes;
            int size = 1 << n;//相当于pow(2, n)
            for (int i = 0; i < size; ++i)
            {
                codes.push_back((i >> 1) ^ i);
            }
            return codes;
        }
    };

我发现把第十行的右移一位codes.push\_back((i >> 1) ^ i)（用了9ms）改成除法运算codes.push\_back((i / 2) ^ i)（用了6ms）运算还变快了！