【leetcode】格雷編碼
題目：
格雷編碼是一個(gè)二進(jìn)制數(shù)字系統(tǒng)瘸彤，在該系統(tǒng)中，兩個(gè)連續(xù)的數(shù)值僅有一個(gè)位數(shù)的差異笛钝。
給定一個(gè)代表編碼總位數(shù)的非負(fù)整數(shù) n质况，打印其格雷編碼序列。即使有多個(gè)不同答案玻靡，你也只需要返回其中一種结榄。
格雷編碼序列必須以 0 開頭。
示例 1:
輸入: 2
輸出:
[0,1,3,2]
解釋:
00 - 0
01 - 1
11 - 3
10 - 2
對(duì)于給定的 n囤捻，其格雷編碼序列并不唯一臼朗。
例如，
[0,2,3,1]
也是一個(gè)有效的格雷編碼序列蝎土。
00 - 0
10 - 2
11 - 3
01 - 1
示例 2:
輸入: 0
輸出:
[0]
解釋: 我們定義
格雷編碼序列必須以 0 開頭视哑。
給定
編碼總位數(shù)為
n 的格雷編碼序列，其長(zhǎng)度為 2n
誊涯。
當(dāng) n = 0 時(shí)挡毅，長(zhǎng)度為 20 = 1。
因此暴构，當(dāng) n = 0 時(shí)跪呈，其格雷編碼序列為 [0]。
思路：
編碼的規(guī)律取逾。什么規(guī)律呢耗绿？通過觀察我們可以發(fā)現(xiàn)，格雷編碼是通過上一級(jí)的編碼得到的砾隅。也就是n個(gè)數(shù)的編碼可以通過n - 1個(gè)數(shù)的編碼得到误阻。
如果n = 1，那么編碼為[0, 1]晴埂；
n = 2堕绩，編碼為[00, 10, 11, 01]；
n = 3邑时，編碼為[000, 100, 110, 010, 011, 111, 101, 001]奴紧；
所以，n級(jí)的編碼的生成晶丘，是從n - 1編碼的最后一個(gè)編碼開始倒序遍歷黍氮，每遍歷一個(gè)編碼，就將這個(gè)編碼+1后的碼字添加到結(jié)果列表的后面浅浮，然后再將這個(gè)編碼+0沫浆。
比如，n = 2滚秩，編碼為[00, 10, 11, 01]专执，倒序遍歷，得到：
01郁油，+1后生成新的碼字添加到后面本股，再對(duì)01+0攀痊，結(jié)果列表變成[00, 10, 11, 010, 011]；
接著向前遍歷拄显，對(duì)11做與上一步相同的處理苟径，結(jié)果列表變成[00, 10, 110, 010, 011, 111]；
最后躬审，結(jié)果列表變?yōu)閇000, 100, 110, 010, 011, 111, 101, 001]棘街。這樣生成的編碼就是符合格雷編碼條件的。也就是說(shuō)承边，n級(jí)格雷編碼是由n - 1級(jí)格雷編碼生成的遭殉，這是很典型的遞歸思想。
最后博助，把二進(jìn)制的字符轉(zhuǎn)換成十進(jìn)制整數(shù)就行险污。
根據(jù)這種規(guī)律，保持首位1不變翔始，后面的位依次前一位異或即可罗心。
比如n = 2，初始化res=[0]
i = 0時(shí),change = 1 << 0 = 1城瞎。cur = 1-1 = 0, res.get(0) ^ change = 1, res.add(1)渤闷。此時(shí)res = [0,1]。
i = 1時(shí),change = 1 << 1 = 2脖镀。cur = 2-1 =1, res.get(1)^change = 1^2 = 3,res.add(3)飒箭。
cur = 0, res.get(0)^change = 0^2 = 2,res.add(2)。
java代碼：
class Solution {
public List<Integer> grayCode(int n) {
List<Integer> res = new ArrayList<>();
res.add(0);
int cur;
for(int i=0;i<n;i++){
int change = 1 << i;
cur = res.size()-1;
while(cur >= 0){
res.add(res.get(cur)^change);
cur--;
}
}
return res;
}
}
