腾讯2016研发工程师编程题及答案(1).pdf

文档介绍：在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同， 则
称这种编码为格雷码(Gray Code)，请编写一个函数，使用递归的方法生
成 N 位的格雷码。
给定一个整数 n，请返回 n 位的格雷码，顺序为从 0 开始。
测试样例：
1
返回：
["0","1"]
1 //方法一：递归
2 //递归的思路就是 n 位 gray 码是由 n-1 位 gray 码生成，举个例子简单一些：
3 //比如求 n=3 的 gray 码，首先知道 n=2 的 gray 码是(00,01,11,10)
4 //那么 n=3 的 gray 码其实就是对 n=2 的 gray 码首位添加 0 或 1 生成的，添加 0 后变成
5 (000,001,011,010)
6 //添加 1 后需要顺序反向就变成(110,111,101,100)
7 //组合在一起就是(000,001,011,010,110,111,101,100)
8 class GrayCode
9 { public:
10 vector<string> getGray(int n) {
11 // write code here
12 vector<string> gray;
13 if(n == 1){
14 ("0");
15 ("1");
16 return gray;
17 }
18 vector<string> last_gray = getGray(n-1);
19 for(int i = 0; i < (); i++)
20 ("0"+last_gray[i]);
21 for(int i = ()-1; i >= 0; i--)
22 ("1"+last_gray[i]);
23
24 return gray;
25 }
26 };
27
28 //方法二：利用公式 G(n