Gray Code
题目:
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, find the sequence of gray code. A gray code sequence must begin with 0 and with cover all 2n integers.
Example: Given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2
分析:
这应该是一道数学题,gray code的生成方式可以看
大意就是n = 2的情况下,复制一遍,反序。把正序部分前面加入0,把反序部分前面加入1,最后把两部分连起来,得到的就是n = 3的格雷码。
编程上这道题目注意两个事情,
(1) 两个vector链接起来的做法是用insert()
forward.insert(forward.end(), backward.begin(), backward.end() );
(2) 把101010字符串,通过二进制转化为int的时候,stoi()的用法是
int temp = stoi(forward[i], NULL, 2);
中间必须有个空指针,不知道干嘛用的,需要查reference。
解法:
class Solution {
public:
/**
* @param n a number
* @return Gray code
*/
vector<int> grayCode(int n) {
// Write your code here
vector<int> res;
if (n == 0) {
res = {0};
return res;
}
if (n == 1) {
res = {0, 1};
return res;
}
vector<string> forward = {"0", "1"};
for (int i = 2; i <= n; i++) {
// reverse previous result
vector<string> backward = forward;
reverse(backward.begin(), backward.end() );
// insert 0 to forward, insert 1 to backward
for (int j = 0; j < forward.size(); j++) {
forward[j].insert(forward[j].begin(), '0');
backward[j].insert(backward[j].begin(), '1');
}
forward.insert(forward.end(), backward.begin(), backward.end() );
}
for (int i = 0; i < forward.size(); i++) {
int temp = stoi(forward[i], NULL, 2);
res.push_back(temp);
}
return res;
}
};