Question
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].
Difficulty:Medium
Category:Backtracking
Analyze
这到题目是关于格雷码的,难点也就是理解格雷码的转换过程。格雷码的转换过程可以如下图所示:
图片来自于:[LeetCode] Gray Code 格雷码
这个图片清晰的说明了格雷码的生成规律,随着n
的变化,前面n-1
之前就存在的项目都是在前面加上0,这些项目的数值是不会变化的,而后面的是和前面的对称相反的,所以在这里进行处理就可以得到完整的格雷码转换之后的vector了。
Solution
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> res;
res.emplace_back(0);
for (int i = 0; i < n; ++i) {
int n = res.size();
for (int j = n - 1; j >= 0; --j) {
res.emplace_back(res[j] | 1 << i);
}
}
return res;
}
};