Leetcode解题: Gray Code (89)

发表于 | 分类于

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:

1
2
3
4
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.

解法1： Recursive O(2^N)

这题一开始没有思路， 对于没思路的可以考虑多写几个最简单的情况的结果来找规律。本题就是一个列子。如果我们把n = 1， n = 2, n = 3的结果写出来就一目了然了。

1
2
3
n = 1
0
1

1
2
3
4
5
n = 2
00
01
11
10
1
2
3
4
5
6
7
8
9
n = 3
000
001
011
010
110
111
101
100

可以发现，对于n的结果，有2^n个数，前2^n-1个数来自于n-1的结果，后一半的数是把n-1的结果倒序后最高位（n)位上加1即可。
有了这个结论，写程序就比较简单了。复杂度应该是O（2^N)

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<int> grayCode(int n) {
        
        if (n == 0) {
            return vector<int> {0};
        }
        if (n == 1) {
           return vector<int> {0,1};
        }
        
        vector<int> previous = grayCode(n - 1);
        vector<int> res;
        
        // add previous level
        for (int i = 0; i < previous.size(); ++i) {
            res.push_back(previous[i]);
        }
        
        for (int i = previous.size() - 1; i >= 0; --i) {
            // add one to the high bits
            int temp =  previous[i] | (1 << n - 1);
            res.push_back(temp);
        }
        
        return res;
    }
};

Java

1