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.
Example 1:
Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.00 - 0
10 - 2
11 - 3
01 - 1
Example 2:
Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
Therefore, for n = 0 the gray code sequence is [0].题源：here；完整实现：here
思路：
两种思路，一种事手动生成需要的格雷码，一种事根据公式（来自维基百科）。
1 手动生成
我们建立一个hash表，里面存放已经生成的gray码，生成gray码很简单：与当前gray码有一个位置不同。代码如下：
vector grayCode(int n) {
string grayCode(n, '0');
vector result;
unordered_map records;
result.push_back(0);
records[grayCode]++;
int total = int(pow(2, n));
for (int i = 0;
i < total;
i++){
for (int j = 0;
j < n;
j++){
string temp = grayCode;
temp[j] = temp[j] == '0' ? '1' : '0';
if (records[temp] == 0){
records[temp]++;
int num = strtol(temp.data(), NULL, 2);
result.push_back(num);
grayCode = temp;
break;
}
}
} return result;
} 2 公式
vector grayCode2(int n){
vector result;
int size = 1 << n;
for (int i = 0;
i < size;
i++){
result.push_back(i ^ (i >> 1));
}
return result;
} 纪念贴图：
【LeetCode89 Gray Code 格雷码 C++】
