笔试刷题-腾讯2018-08-18

题目描述：

/**
在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，
则称这种编码为格雷码(Gray Code)，请编写一个函数，使用递归的方法生成N位的格雷码。
给定一个整数n，请返回n位的格雷码，顺序为从0开始。
测试样例：
1
返回：["0","1"]
*/

思路如下：

用递归思想找规律即可
f(n-1)表示n-1个的序列
产生f(n)
先顺序遍历f(n-1)在头部加0
再倒序遍历f(n-1)在头部加1

代码如下：

class GrayCode {
public:
    vector<string> getGray(int n) {
        // write code here
        vector<string> res;
        if(n==1){
            res.push_back("0");
            res.push_back("1");
            return res;
        }
        else{
            vector<string> preRes=getGray(n-1);
            for(int i=0; i<preRes.size(); i++){
                res.push_back("0"+preRes[i]);
            }
            for(int i=preRes.size()-1; i>=0; i--){
                res.push_back("1"+preRes[i]);
            }
            return res;
        }
    }
};