題目
格雷編碼是一個(gè)二進(jìn)制數(shù)字系統(tǒng)型将，在該系統(tǒng)中寂祥，兩個(gè)連續(xù)的數(shù)值僅有一個(gè)位數(shù)的差異。
給定一個(gè)代表編碼總位數(shù)的非負(fù)整數(shù) n七兜，打印其格雷編碼序列丸凭。格雷編碼序列必須以 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]。
思路
1.這道題感覺是一個(gè)找規(guī)律的題目迄薄，找到規(guī)律后就很好求解琅关，感覺不是一道回溯的題。
對(duì)于n=2讥蔽，它的結(jié)果包括n=1時(shí)的結(jié)果左邊補(bǔ)零涣易，以及逆序遍歷n=1時(shí)的結(jié)果左邊補(bǔ)1，
規(guī)律如下圖,列出了n=1,n=2,n=3時(shí)的情況冶伞。
vector<int> grayCode(int n) {
vector<int>result(1);
for (int i = 0; i < n; i++)
{
for (int j = result.size() - 1; j >=0; j--)
{
result.push_back((1 << i) + result[j]);
}
}
return result;
}
2都毒、解法二就涉及到gray code的數(shù)學(xué)知識(shí)了，要是知道這個(gè)數(shù)學(xué)知識(shí)碰缔，可以在幾分鐘之內(nèi)就解出這道題。
格雷碼可以由對(duì)應(yīng)的十進(jìn)制數(shù)求出：grayCode=i^i>>1
vector<int> grayCode2(int n)
{
vector<int> result;
for (int i = 0; i < 1 << n;i++)
{
result.push_back(i ^ i >> 1);
}
return result;
}
解法參考https://blog.csdn.net/u012501459/article/details/46790683
