LeetCode 89. 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, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

格雷码是一个二进制数字系统，其中两个连续的值只在一个位上有所不同。
给定一个非负整数n代表代码中的比特总数，打印格雷码序列。格雷码序列必须以0开头。

解题思路：

如下为3位的格雷码序列，可以看出除了最高位（左边第一位），格雷码的位元完全上下对称（看下面列表）。

比如第一个格雷码与最后一个格雷码对称（除了第一位），第二个格雷码与倒数第二个对称，以此类推。

　　000
　　001
　　011
　　010
　　110
　　111
　　101
　　100

　　依照此规则，我们可以在n-1位格雷码的前面加上0，得到n位格雷码前半部分的格雷码序列；然后按照原

序列从后往前，依次在前面加上1，得到n位格雷码的后半部分序列。将两者合起来即可得到n位格雷码序列。

如1位格雷码：

　　0,1

依照规则2位格雷码序列为：

　　00,01,11,10

3位格雷码序列为：

　　000,001,011,010,110,111,101,100

4位格雷码序列为：

　　0000,0001,0011,0010,0110,0111,0101,0100,1100,1101,1111,1110,1010,1011,1001,1000

具体代码如下：

 1 class Solution {
 2 public:
 3     vector<int> grayCode(int n) {
 4         vector<int> vec;
 5         vec.push_back(0);
 6         int last = 0;
 7         int t = 1;
 8         for (int i = 1; i <= n; i++)
 9         {
10             last = vec.size()-1;
11             for (int j = last; j >=0; j--)
12             {
13                 vec.push_back(vec[j] + t);
14             }
15             t = t << 1;
16         }
17         return vec;
18     }
19 };

 

posted on 2018-02-06 09:05 IT_Amateur 阅读(…) 评论(…) 编辑 收藏

版权声明：本文为IT-Amateur原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/IT-Amateur/p/8420754.html