問題：

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,1,3,2] 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.

大意：

格雷碼是一種二進制編碼系統(tǒng)，相鄰的兩個值之間只有一位是不同的。
給出一個非負數(shù)n，表示編碼的總位數(shù)，輸出格雷碼序列。格雷碼必須從0開始。
比如，給出n=2，返回[0,1,3,2]。它的格雷碼序列是：

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

注意：
對于給出的n，格雷碼序列并不是唯一的。
比如，[0,2,3,1]也是一種滿足上面要求的序列。
現(xiàn)在，判斷程序只支持一種格雷碼序列，很抱歉。

思路：

格雷碼是很經(jīng)典的問題，規(guī)則其實很簡單，在二進制形式下，任何響鈴的兩個值的二進制表示形式只有一位是不同的，我們可以找找規(guī)律。

一位就是簡單的：0,1

兩位是：00,01,11,10

三位是：000,001,011,010,110,111,101,100

發(fā)現(xiàn)什么規(guī)律沒有？我們把一位的兩個數(shù)，前面加上0，就是二位的頭兩個數(shù)，前面加上1再反序，就是二位的后兩個數(shù)。把二位的前面加上0，就是三位的頭四個數(shù)，把二位的前面加上1再反過來，就是三位的后四個數(shù)。

也就是說，對于每多一位的格雷碼，前面一半的第一位都是0，后面一半的第一位都是1，其余的位，前后兩半正好是中間對稱的，前面一半就是少一位的格雷碼序列，后面一半時把其反序。

知道這個規(guī)律就好做了，我們可以遞歸來做，每次取n-1位的格雷碼來做上述操作，對于一位的格雷碼，直接賦值是0,1就可以了。

不過題目要求返回的是十進制數(shù)，而不是字符串，所以我們最好直接操作十進制數(shù)，這里前面加0其實就不用做什么，前面加1的話可以將1左移n-1位然后與各個數(shù)字相加即可。

注意題目說的n是非負數(shù)，所以要考慮n=0的情況，測試用例的n=0時返回的是0。

代碼（Java）：

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<Integer>();
        if (n == 0) {
            res.add(0);
            return res;
        } else if (n == 1) {
            res.add(0);
            res.add(1);
            return res;
        }
        
        List<Integer> last = grayCode(n-1);
        
        for (int i = 0; i < last.size()*2; i++) {
            if (i < last.size()) res.add(last.get(i));
            else {
                int temp = last.get(last.size()-(i-last.size())-1);
                temp += 1 << (n-1);
                res.add(temp);
            }
        }
        
        return res;
    }
}

合集：https://github.com/Cloudox/LeetCode-Record

查看作者首頁