挨个遍历，傻方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public:
vector<int> grayCode(int n) {
if(n == 0)
return { 0 };
vector<int> ret{ 0 };
vector<int> set(1 << n, 0);
set[0] = 1;
helper(n, ret, set);
return ret;
}
private:
void helper(int n, vector<int>& ret, vector<int>& set)
{
if(ret.size() == 1 << n)
return;
int preNum = ret.back();
for(int i = 0; i < n; ++i)
{
auto tmp = preNum ^ (1 << i);
if(!set[tmp])
{
set[tmp] = 1;
ret.push_back(tmp);
helper(n, ret, set);
}
}
}
};
|
大佬的仙法
镜像构造
贴题解
Gray Code （镜像反射法，图解） - 格雷编码 - 力扣（LeetCode） (leetcode-cn.com)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
vector<int> grayCode(int n) {
int head = 1;
vector<int> ret{ 0 };
for(int i = 1; i <= n; ++i)
{
for(int j = ret.size() - 1; j >= 0; --j)
ret.push_back(ret[j] ^ head);
head <<= 1;
}
return ret;
}
};
|
公式
格雷码的每一位
B是指正常的二进制编码
G(i) = Bi ^ (Bi + 1)换言之就是G(i) = Bi ^ (Bi >> 1)
对于一位如此，对于所有位都如此。
1
2
3
4
5
6
7
8
9
| class Solution {
public:
vector<int> grayCode(int n) {
vector<int> ret;
for(int i = 0; i < (1 << n); ++i)
ret.push_back(i ^ (i >> 1));
return ret;
}
};
|