格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n,打印其格雷编码序列。格雷编码序列必须以 0 开头。
示例 1:
输入: 2 输出:[0,1,3,2]
解释: 00 - 0 01 - 1 11 - 3 10 - 2 对于给定的 n,其格雷编码序列并不唯一。 例如,[0,2,3,1]
也是一个有效的格雷编码序列。 00 - 0 10 - 2 11 - 3 01 - 1
示例 2:
输入: 0 输出:[0] 解释: 我们定义
格雷编码序列必须以 0 开头。给定
编码总位数为n 的格雷编码序列,其长度为 2n
。当 n = 0 时,长度为 20 = 1。 因此,当 n = 0 时,其格雷编码序列为 [0]。
题目标签:Backtracking
题目链接:LeetCode / LeetCode中国
将x的二进制第n位取反:x^(i<<n)
Language | Runtime | Memory |
---|---|---|
cpp | 8 ms | 995.3 KB |
class Solution {
public:
vector<int> res;
unordered_set<int> vt;
void dfs(int n, int x) {
if (res.size() == pow(2, n)) {
return;
}
for (int i=0; i<n; ++i) {
int nx = x ^ (1 << i);
if (!vt.count(nx)) {
res.emplace_back(nx);
vt.emplace(nx);
dfs(n, nx);
}
}
}
vector<int> grayCode(int n) {
int start = 0;
res.emplace_back(start);
vt.emplace(start);
dfs(n , start);
return res;
}
};