89. Gray Code

Leetcode Backtracking

题目

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 的wikipedia页面在此。

例举grey code序列，并找规律 :

以$n = 3$为例，grey code中前4个包括了$n = 2$的所有gray code。后4个则是前4个逆序后加上$2^2$。

推广：$n = i$的grey code的前一半包括了$n = i-1$的所有grey code，而后一半则为前一半逆序后加上$2^{(i-1)}$。

在写程序的过程中，特别要注意res的index 以及$i$，$j$的关系。主要是细节问题。

class Solution {
public:

    // a non-negative integer n: the total number of bits in the code
    // print the sequence of gray code. 
    // A gray code sequence must begin with 0.
    vector<int> grayCode(int n) {
        vector<int> res;
        res.push_back(0); // when n=0, gray code = 0

        for(int i=1; i<= n; i++){
            for (int j=pow(2,i-1); j< pow(2,i); j++){
                res.push_back(res[pow(2,i)-j-1]+pow(2, i-1));
            }
        }
        return res;
    }
};

其实还有一种非常简单的方法，直接从数学角度出发的，但需要首先了解gray code。其实在二进制数和gray code之间有转换关系：

/*
 * This function converts an unsigned binary
 * number to reflected binary Gray code.
 *
 * The operator >> is shift right. The operator ^ is exclusive or.
 */
unsigned int BinaryToGray(unsigned int num)
{
    return num ^ (num >> 1); //与右移一位的数字按位异或
}