89. Gray Code
提交网址: https://leetcode.com/problems/gray-code/
Total Accepted: 58554 Total Submissions: 161869 Difficulty: Medium ACrate: 36.2%
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0 01 - 1 11 - 3 10 - 2
Note: For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
分析:
格雷码 有个相应的数学公式,整数n的格雷码是n^(n/2).
方法1: 最简单的方法,利用数学公式,对从0~2^n-1的所有整数,转化为格雷码。 方法2: n比特的格雷码,可以递归地从n-1比特的格雷码生成。如下图所示:
Gray Code 0 = 0, 下一项是toggle最右边的bit(LSB), 再下一项是toggle最右边值为 “1” bit的左边一个bit。然后重复
如: 3bit
Gray Code: 000, 001, 011, 010, 110, 111, 101, 100, 最右边值为 “1” 的bit在最左边了,结束。
Binary : 000, 001, 010, 011, 100, 101, 110, 111
再者就是Binary Code 转换为Gray Code了。
如:
Binary Code :1011 要转换成Gray Code
1011 = 1(照写第一位), 1(第一位与第二位异或 1^0 = 1), 1(第二位异或第三位, 0^1=1), 0 (1^1 =0) = 1110
其实就等于 (1011 >> 1) ^ 1011 = 1110
AC代码:
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> emptyArr(0);
if(n<0) return emptyArr; // 输入异常时,即n为负整数时的处理办法...
if(n>=0)
{
int size=1<<n;
vector<int> NumArr(size,0);
int gNum=0;
for(int i=0;i<size;i++)
{
gNum=i ^ i>>1; // 数学公式G[i]=i ^ i/2,gNum是一个格雷码对应的二进制数,存储时变成int(十进制)
NumArr[i]=gNum;
}
return NumArr;
}
}
};
/* 以下为测试 */
/*
int main()
{
int n,j;
vector<int> display;
cin>>n;
Solution sol;
display=sol.grayCode(n);
for(j=0;j<display.size();j++)
{
cout<<display[j]<<" ";
}
cout<<endl;
return 0;
}*/