leetcode:Gray Code -电脑资料

    一、 题目

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

leetcode:Gray Code

    例如：输入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<int>grayCode(int n) {        int num = 1<<n;		vector<int>ans;		ans.reserve(num);		for(int i=0;i<num;i++)			ans.push_back(i^(i>>1));		return ans;     }};

class Solution {public:    vector<int>grayCode(int n) {        vector<int>ans;        if(n==0){        	ans.push_back(0);        	return ans;        }        vector<int>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;    }};