leetcode:Gray Code

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;
    }
};