Question

89. Gray Code

Solution

思路：

n = 0   0
n = 1   0   1
n = 2  00  01  10  11
n = 3 000 001 010 011 100 101 110 111 

Java實現：

public List<Integer> grayCode(int n) {List<Integer> list = new ArrayList<>();grayCode(n, 0, list);return list;
}void grayCode(int n, int cur, List<Integer> list) {if (cur == 0) {list.add(0);} else if (cur == 1) {list.add(1);} else {int tmpSize = list.size();for (int i = tmpSize - 1; i >= 0; i--) {// int tmp = 1 << (cur - 1);// System.out.println(tmp + "\t" + list.get(i) + "\t" + (list.get(i) | tmp));list.add(list.get(i) | (1 << (cur - 1)));}}if (cur < n) grayCode(n, cur + 1, list);
}

Reference

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

一位就是簡單的：0,1

兩位是：00,01,11,10

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

發現什么規律沒有？我們把一位的兩個數，前面加上0，就是二位的頭兩個數，前面加上1再反序，就是二位的后兩個數。把二位的前面加上0，就是三位的頭四個數，把二位的前面加上1再反過來，就是三位的后四個數。

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

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

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

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