LeetCode 格雷码序列的生成
问题概述：
在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码。
2位数的格雷码序列：
00 : 0
01 : 1
11 : 3
10 : 2
找规律：
如果要求n位的格雷码，先要求出n-1位的格雷码。
循环上一次格雷码的每一位，都会生成两个新的格雷码：
统计'1'出现的次数
如果为偶数： 两个新格雷码分别为xxx1和xxx0
如果为奇数： 两个新格雷码分别为xxx0和xxx1
以3位格雷码为例：
由00得：
000 = 00+(0)
001 = 00+(1)
由01得：
011 = 01+(1)
010 = 01+(0)
由11得：
110 = 11+(0)
111 = 11+(1)
由10得：
101 = 10+(1)
100 = 10+(0)
在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码。
2位数的格雷码序列：
00 : 0
01 : 1
11 : 3
10 : 2
找规律：
如果要求n位的格雷码，先要求出n-1位的格雷码。
循环上一次格雷码的每一位，都会生成两个新的格雷码：
统计'1'出现的次数
如果为偶数： 两个新格雷码分别为xxx1和xxx0
如果为奇数： 两个新格雷码分别为xxx0和xxx1
以3位格雷码为例：
由00得：
000 = 00+(0)
001 = 00+(1)
由01得：
011 = 01+(1)
010 = 01+(0)
由11得：
110 = 11+(0)
111 = 11+(1)
由10得：
101 = 10+(1)
100 = 10+(0)
然后把新格雷码添加到序列用于下一次格雷码序列的计算。
实现代码：
public class Solution {
public IList<int> GrayCode(int n) {
if(n < 0){
return new List<int>();
}
if(n == 0){
return new List<int>{0};
}
if(n == 1){
return new List<int>(){0,1};
}
if(n == 2){
return new List<int>{0,1,3,2};
}
var r = new List<string>(){"00","01","11","10"};
for(var i = 3;i <= n; i++){
var tmp = new List<string>();
for(var j = 0;j < r.Count; j++){
var countOne = 0;
foreach(var c in r[j]){
if(c == '1'){
countOne ++;
}
}
if(countOne % 2 == 0){
tmp.Add(r[j]+"0");
tmp.Add(r[j]+"1");
}
else{
tmp.Add(r[j]+"1");
tmp.Add(r[j]+"0");
}
}
r = tmp;
}
var ret = new List<int>();
foreach(var s in r){
var num = Convert.ToInt32(s,2);
ret.Add(num);
}
return ret;
}
}