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.
链接
格雷码
000 001 011 010 ↑
110 ↓ 111 101 100
可看成是上下对称的2部分。上半部分是n=2时候的结果再在最高位加”0”的结果。下半部分是n=2时候的结果逆序之后再在最高位加”1”的结果
class Solution { public: vector<int> grayCode(int n) { vector<int> res; int c; res.push_back(0); for(int i=0;i<n;i++){ c=1<<i; int sz=res.size(); //添加镜面反射的那一部分(最高位加1) //要反着遍历才能对称 for(int j=sz-1;j>=0;j--){ res.push_back(res[j]+c); } } return res; } };ref: https://yq.aliyun.com/articles/3875
