LeetCode/格雷编码
n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
- 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
- 第一个整数是 0
- 一个整数在序列中出现 不超过一次
- 每对 相邻 整数的二进制表示 恰好一位不同 ，且
- 第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n ，返回任一有效的 n 位格雷码序列
1.回溯法(超时)
回溯法
class Solution {
public:
//应该是异或运算结果是2的n次幂
unordered_set map_;
bool cut = false;
vector grayCode(int n) {
for(int i=0;i flag(num,false);
vector Code;
backtrack(Code,0,flag,num);
return Code;
}
void backtrack(vector&list,int index,vectorflag,int num){
if(index==num){cut=true;return;}
for(int i=0;i 2.格雷码公式
class Solution {
public:
vector grayCode(int n) {
vector ret(1 << n);
for (int i = 0; i < ret.size(); i++) {
ret[i] = (i >> 1) ^ i;
}
return ret;
}
};
3.镜像反转
class Solution {
public:
vector grayCode(int n) {
vector ret;
ret.reserve(1 << n);
ret.push_back(0);
for (int i = 1; i <= n; i++) {
int m = ret.size();
for (int j = m - 1; j >= 0; j--) {
ret.push_back(ret[j] | (1 << (i - 1)));
}
}
return ret;
}
};