问题概述:
在一组数的编码中,若随意两个相邻的代码仅仅有一位二进制数不同。则称这样的编码为格雷码。
在一组数的编码中,若随意两个相邻的代码仅仅有一位二进制数不同。则称这样的编码为格雷码。
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; }
}