Leetcode 89. Gray Code

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Gray Code

2. Solution

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> result;
bitset<32> code;
traverse(result, code, n - 1);
return result;
}
private:
void traverse(vector<int>& result, bitset<32>& code, int pos) {
if(pos < 0) {
int value = code.to_ulong();
result.push_back(value);
return;
}
traverse(result, code, pos - 1);
code.flip(pos);
traverse(result, code, pos - 1);
}
};
  • Version 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> result;
int code = 0;
traverse(result, code, n - 1);
return result;
}
private:
void traverse(vector<int>& result, int& code, int pos) {
if(pos < 0) {
result.push_back(code);
return;
}
traverse(result, code, pos - 1);
code ^= (1 << pos);
traverse(result, code, pos - 1);
}
};

Reference

  1. https://leetcode.com/problems/gray-code/description/
如果有收获,可以请我喝杯咖啡!