leetcode:Gray Code

一、 题目

输入一个数n，将这个数的格雷码输出。

例如：输入2，返回{0,1,3,2}

二、 分析

1、二进制码->格雷码（编码）：从最右边一位起，依次将每一位与左边一位异或（XOR），作为对应格雷码该位的值，最左边一位不变（相当于左边是0）；（对应以上代码的for循环里的循环体）。

格雷码->二进制码（解码）：从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）。

2、找规律

以3位格雷码为例。

0 0 0

0 0 1

0 1 1

0 1 0

1 1 0

1 1 1

1 0 1

1 0 0

可以看到第n位的格雷码由两部分构成，一部分是n-1位格雷码，再加上1<<(n-1)和n-1位格雷码的逆序的和。

如下：

（0）00

（0）01

（0）11

（0）10

100+010=110

100+011=111

100+001=101

100+000=100

class Solution {
public:
    vector
  
    grayCode(int n) {
        int num = 1<
   
     ans; ans.reserve(num); for(int i=0;i
    
     >1)); return ans; } }; 
    
   
  

class Solution {
public:
    vector
  
    grayCode(int n) {
        vector
   
     ans; if(n==0){ ans.push_back(0); return ans; } vector
    
      res = grayCode(n-1); int len = res.size()-1; int adder = 1<<(n-1); for(int i=len;i>=0;i--){ res.push_back(adder+res[i]); } return res; } };