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 - 2Note:
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.
Solution: I didn't figure it out until I saw the construction method of the gray code:-( . Anyway, here has enough info. for you to solve this problem.
/*******************************SOLUTION 1***********************************/
/*See the definition of gray code: http://en.wikipedia.org/wiki/Gray_code*/ class Solution { public: vector<int> grayCode(int n) { // Note: The Solution object is instantiated only once and is reused by each test case. vector<int> ret; if(n<0) return ret; ret.push_back(0); for(int i=0; i<n; ++i){ int s = ret.size(); int highDigit = 1<<i; for(int j = s-1; j>=0; --j){ ret.push_back(ret[j]+highDigit); } } return ret; } };/*******************************SOLUTION 2***********************************/
/*See the definition of gray code: http://en.wikipedia.org/wiki/Gray_code*/ class Solution { public: vector<int> grayCode(int n) { // Note: The Solution object is instantiated only once and is reused by each test case. vector<int> ret; if(n<0) return ret; int size = 1<<n; for(int i=0; i<size; ++i) ret.push_back(i>>1 ^ i); return ret; } };
No comments:
Post a Comment