算法与数据布局（格雷编码）

标题

思绪

起首我们先看一下格雷编码的一些环境，为了一会方便明白，我们看它的二进制环境。
当n=1时，输出[0，1]
当n=2时，输出[00,01,11,10]
当n=3时，输出[000, 001, 011, 010, 110, 111, 101, 100]
我们可以看到2的前半部分就是1，3的前半部分就是2。
以是我们只必要求后半部分即可，
格雷码的天生有一个递推公式。已知n-1位的格雷码，怎样得到n位的？方法是，起首将n-1位的格雷码列表逆序，然后每个数的最高位设为1，然后拼接到原来的列表背面。比方，n=1的格雷码是0,1。n=2的时间，将之前的逆序是1,0，然后前面加上最高位1，酿成11,10，然后拼接到原来的00,01背面，得到00,01,11,10，对应十进制的0,1,3,2。
总结一下，就是：

•         将k-1位序列逆序。
  
•         对逆序后的每个元素，在最高位（即第k-1位）添加1。
  
•         将新天生的序列追加到原序列之后。
  

代码详解

起首，界说一个ans用来存储格雷码序列。
ans.reserve是将ans的capacity容量扩大，n位格雷码有2^n个序列，以是就给他2^n的空间。
至于内里为什么是1<<n。
它的意思就是把1向左移动n位
n=1, 移动完：10              2^1=2
n=2, 移动完：100            2^2=4
n=3, 移动完：1000          2^3=8
接着将内里的变量初始化为0。
for(int i=1;i<=n;i++) 这个是用来逐位构造格雷码的，对于n=1，只会循环一次
int m =ans.size();
这个是求ans现有的元素数

2. for(int j=m-1;j>=0;j--)
3.             {
4.                 ans.push_back(ans[j] | (1 << (i-1)));
5.             }

复制代码

这个就是对内里现有的数举行倒序访问。
ans.push_back(ans[j] | (1 << (i-1)));
这个是1左移i-1位与原有的数相或。如果i=1,就是1左移0位，实在他就是用来将第i-1位设为1，并添加到结果中。
当n=1时，输出[0，1]
当n=2时，输出[00,01,11,10]
对于这个例子，n=2就是将第二位设为1，分别是11，10并添加到序列中，由于是逆序，以是先给1加，后给0加。
末了返回ans即可。
代码

1. class Solution {public:    vector<int> grayCode(int n) {        vector<int> ans;        ans.reserve(1<<n);        ans.push_back(0);        for(int i=1;i<=n;i++)        {            int m =ans.size();            
2. for(int j=m-1;j>=0;j--)
3.             {
4.                 ans.push_back(ans[j] | (1 << (i-1)));
5.             }        }        return ans;    }};

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告