【leetcode-89 动态规划】 格雷编码
（
中等难度题（×)
-背答案题（√）
）
格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。
示例 1:
输入: 2 输出:[0,1,3,2]解释: 00 - 0 01 - 1 11 - 3 10 - 2 对于给定的 n，其格雷编码序列并不唯一。 例如，[0,2,3,1]也是一个有效的格雷编码序列。 00 - 0 10 - 2 11 - 3 01 - 1
示例 2:
输入: 0 输出:[0] 解释: 我们定义格雷编码序列必须以 0 开头。给定编码总位数为n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。 因此，当 n = 0 时，其格雷编码序列为 [0]。
链接：https://www.nowcoder.com/questionTerminal/55dddb4cdf074fefba653ff523e42346
来源：牛客网
当n=1时，为[0,1]当n=2时，为[00,01,11,10]当n=3时，为[000,001,011,010,110,111,101,100]由此可以看出新的序列其实是在前面序列基础上插入新的值其中前半部分的数值不变，后半部分的数值为上个序列中每个元素第n个位变1，逆向插入//随着n变大，前面的数不用动，后面的数倒着拿出来再在首部加1即可 class Solution { public: vector<int> grayCode(int n) { vector<int> result; result.push_back(0); for (int i = 0; i < n; i++) { const int hight_bit = 1 << i; for (int j = result.size() - 1; j >= 0; j--) //第二遍反着遍历，形成对称 result.push_back(hight_bit | result[j]); } return result; } };