leetcode_89

发表于   |   分类于

Gray Code

题目戳这

题意

给定n为的格雷码的位数，求返回的格雷码代表的十进制数序列。

解法

有两种方法，一种是回溯，一种是利用格雷码的定义。

回溯的话我们多写几个看看。

当n=1时，返回 0, 1

当n=2时，返回 00, 01, 11, 10

当n=3时，返回 000,001,011,010,110,111,101,100

从上面我们可以发现，n=3的序列是可以由n=2构成的，n=3的前一半序列是n=2序列前面加个0，n=3的后一半序列是n=2序列前面加个1的逆序。由这个定义我们就可以用dfs来得出最后的结果。

还有一个是格雷码的定义，从二进制到格雷码的转换是通过亦或相邻二进制的位数来得到的 。

比如一个二进制为 1001,那么它的格雷码为

1^0 = 1 0^0 = 0 0^1 = 1 1^0 = 1，
则为1101，最后一个0是最高位补上去的。

其实说了这么多，求一个数x的格雷码的十进制表示就是 x^(x>>1)即可。

代码

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
# dfs
class Solution(object):
    def dfs(self,n):
        grayCode = [""]*pow(2,n)
        if n == 1:
            return ['0','1']
        code = self.dfs(n-1)
        for i in range(len(code)):
            grayCode[i] = '0' + code[i]
            grayCode[len(grayCode)-i-1] = '1' + code[i]
        return grayCode
        pass
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        if n == 0:
            return [0]
        ans = self.dfs(n)
        ans = map(lambda x:int(x,2), ans)
        return ans
1
2
3
4
5
6
7
8
# 定义
class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        return [(i>>1)^i for i in range(1<<n)]