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的生成方式可以看

http://www.geeksforgeeks.org/given-a-number-n-generate-bit-patterns-from-0-to-2n-1-so-that-successive-patterns-differ-by-one-bit/

大意就是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;
    }
};