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, find the sequence of gray code. A gray code sequence must begin with 0 and with cover all 2nintegers.
Notice
For a given n, a gray code sequence is not uniquely defined.
[0,2,3,1] is also a valid gray code sequence according to the above definition.
Example
Given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2
Challenge
O(2n) time.
LeetCode上的原题，请参见我之前的博客Gray Code。
解法一：
class Solution { public: /** * @param n a number * @return Gray code */ vector<int> grayCode(int n) { vector<int> res; for (int i = 0; i < pow(2, n); ++i) { res.push_back((i >> 1) ^ i); } return res; } };
解法二：
class Solution { public: /** * @param n a number * @return Gray code */ vector<int> grayCode(int n) { vector<int> res{0}; for (int i = 0; i < n; ++i) { int size = res.size(); for (int j = size - 1; j >= 0; --j) { res.push_back(res[j] | (1 << i)); } } return res; } };
解法三：
class Solution { public: /** * @param n a number * @return Gray code */ vector<int> grayCode(int n) { vector<int> res{0}; int len = pow(2, n); for (int i = 1; i < len; ++i) { int pre = res.back(); if (i % 2 == 1) { pre = (pre & (len - 2)) | (~pre & 1); } else { int cnt = 1, t = pre; while ((t & 1) != 1) { ++cnt; t >>= 1; } if ((pre & (1 << cnt)) == 0) pre |= (1 << cnt); else pre &= ~(1 << cnt); } res.push_back(pre); } return res; } };
解法四：
class Solution { public: /** * @param n a number * @return Gray code */ vector<int> grayCode(int n) { vector<int> res{0}; unordered_set<int> s; stack<int> st; s.insert(0); st.push(0); while (!st.empty()) { int t = st.top(); st.pop(); for (int i = 0; i < n; ++i) { int k = t; if ((k & (1 << i)) == 0) k |= (1 << i); else k &= ~(1 << i); if (s.count(k)) continue; s.insert(k); st.push(k); res.push_back(k); break; } } return res; } };
解法五：
class Solution { public: /** * @param n a number * @return Gray code */ vector<int> grayCode(int n) { vector<int> res; unordered_set<int> s; helper(n, s, 0, res); return res; } void helper(int n, set<int>& s, int out, vector<int>& res) { if (!s.count(out)) { s.insert(out); res.push_back(out); } for (int i = 0; i < n; ++i) { int t = out; if ((t & (1 << i)) == 0) t |= (1 << i); else t &= ~(1 << i); if (s.count(t)) continue; helper(n, s, t, res); break; } } };
本文转自博客园Grandyang的博客，原文链接：格雷码[LintCode] Gray Code ，如需转载请自行联系原博主。
