题目描述
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.
Example1:
Input: 2 Output: [0,1,3,2] Explanation: 00 - 0 01 - 1 11 - 3 10 - 2
For 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
Example2:
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].
解题思路
- 如果已知n-1位的序列，那么n位的序列求法是有规律的
- 比如2位的序列[00,01,11,10]变成3位的话只需要先在高位加0变成[000,001,011,010]，再逆序在高位加1即[110,111,101,100]
- 合起来就是3位的序列了，[000,001,011,010,110,111,101,100]。
class Solution {
public:
vector<int> grayCode(int n) {
if(n < 0){
return {};
}
vector<int> res;
res.push_back(0);
for(int i = 0; i < n; i++){
int size = res.size();
for(int j = size - 1; j >= 0; j--){
res.push_back(res[j] | 1 << i);
}
}
return res;
}
};
