Python-Study/Leetcode/Gray_Code.py at master · JohnnyHuo/Python-Study · 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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
"""
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:

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.
"""

# Tip: you can use bin(x) to check the binary form of a num

classSolution:
# @return a list of integers
defgray_code(self, n):
ifn==0:
return [0]
return [int(code, 2) forcodeinself.graycode_helper(n)]

defgraycode_helper(self, n):
ifn==1:
return ['0', '1']
prev_code=self.graycode_helper(n-1)
cur_code= []
forcodeinprev_code:
cur_code.append('0'+code)
forcodeinprev_code[::-1]:
cur_code.append('1'+code)
returncur_code

# Using bit
defgrayCode(self, n):
ret= []
i=0
whilei<2**n:
ret.append(i>>1^i)
i+=1
returnret

# Using generator
"""
 def grayCodeGen(self, n, reverse=False):
 if n == 1:
 if reverse:
 yield "1"
 yield "0"
 else:
 yield "0"
 yield "1"
 else:
 if reverse:
 # all the "1"s start first
 gcprev = self.grayCodeGen(n-1, False)
 for code in gcprev:
 yield "1" + code
 gcprev = self.grayCodeGen(n-1, True)
 for code in gcprev:
 yield "0" + code
 else:
 # all the "0" start first
 gcprev = self.grayCodeGen(n-1, False)
 for code in gcprev:
 yield "0" + code
 gcprev = self.grayCodeGen(n-1, True)
 for code in gcprev:
 yield "1" + code
"""