Leetcode-Python/Gray Code.py at master · MartinTrojans/Leetcode-Python · GitHub

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
__author__ = 'Martin'

class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        self.ans = []
        self.dfs(n, 0, True)
        return self.ans

    def dfs(self, n, res, left):
        if n == 0:
            self.ans.append(res)
            return
        else:
            if left is True:
                self.dfs(n-1, res*2, True)
                self.dfs(n-1, res*2+1, False)
            else:
                self.dfs(n-1, res*2+1, True)
                self.dfs(n-1, res*2, False)

    def grayCode1(self, n):
        res=[]
        size=1<<n
        for i in range(size):
            res.append((i>>1)^i)
        return res

    def grayCode2(self, n):
        if n == 1:
            return [0, 1]
        size = 1 << n
        last = self.grayCode2(n-1)
        res = [0 for i in range(size)]
        for i in range(len(last)):
            res[i] = last[i]
            res[size-1-i] = last[i] + (1<<(n-1))
        return res


'''
class Solution:
    # @return a list of integers
    def grayCode(self, n):
        res=[]
        size=1<<n
        for i in range(size):
            res.append((i>>1)^i)
        return res
'''

s = Solution()
print(s.grayCode(3))
print(s.grayCode1(3))
print(s.grayCode2(3))