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.

Have you met this question in a real interview? 

Yes

Example

Given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 001 - 111 - 310 - 2

O(2ⁿ) time.

 

LeetCode上的原题，请参见我之前的博客。

 

解法一：

class Solution {public:    /**     * @param n a number     * @return Gray code     */    vector
     
       grayCode(int n) {        vector
      
        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
     
       grayCode(int n) {        vector
      
        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
     
       grayCode(int n) {        vector
      
        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
     
       grayCode(int n) {        vector
      
        res{
   0};        unordered_set
       
         s;        stack
        
          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
     
       grayCode(int n) {        vector
      
        res;        unordered_set
       
         s;        helper(n, s, 0, res);        return res;    }    void helper(int n, set
        
         & s, int out, vector
         
          & 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;        }    }};