Description:
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.
Example 1:
Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.00 - 0
10 - 2
11 - 3
01 - 1
Example 2:
Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
Therefore, for n = 0 the gray code sequence is [0].
Solutions:
My solution:
If n is an even number, every two bits will be treated as a group, and iterate from "00", "01", "11", "10" cyclically. If n is an odd one, the leftmost bit will swing between "0" and "1".
class Solution:
def grayCode(self, n: int) -> List[int]:
if n == 0:
return [0]
if n == 1:
return [0,1]
quotient = n//2
remainder = n%2
shift = {"00":"01","01":"11","11":"10","10":"00"}
def iterate(times,start):
head = start[-times*2-1:-times*2+1]
ls = [head]
for i in range(3):
head = shift[head]
ls.append(head)
if times == 1:
return ls
result = []
for current in ls:
for r in iterate(times-1,start):
result.append(current+r)
start = result[-1]+"0"
return result
binary = iterate(quotient,"00"*quotient+"0")
if remainder == 1:
binary2 = iterate(quotient,binary[-1]+"0")
cache = []
for b in binary:
cache.append("0"+b)
for b in binary2:
cache.append("1"+b)
else:
cache = binary
result = []
for c in cache:
result.append(int(c,2))
return result
Runtime: 32 ms, faster than 96.82% of Python3 online submissions for Gray Code.
Memory Usage: 13.3 MB, less than 28.26% of Python3 online submissions for Gray Code.
Shorter version using "generator"
class Solution:
def grayCode(self, n: int) -> List[int]:
if n == 0:
return [0]
if n == 1:
return [0,1]
quotient = n//2
remainder = n%2
shift = ["00", "01", "11", "10"]
def iterate(times,start):
index = shift.index(start[-times*2-1:-times*2+1])
ls = shift[index:] + shift[:index]
if times == 1:
for l in ls:
yield l
else:
for current in ls:
for r in iterate(times-1,start):
cache = current+r
yield cache
start = cache+"0"
result = []
for b in iterate(quotient,"00"*quotient+"0"):
result.append(int("0"+b,2))
if remainder == 1:
for b in iterate(quotient,"0"+bin(result[-1])[2:]+"0"):
result.append(int("1"+b,2))
return result
Runtime: 40 ms, faster than 66.83% of Python3 online submissions for Gray Code.
Memory Usage: 13.2 MB, less than 49.07% of Python3 online submissions for Gray Code.
sample 32 ms submission:https://www.cnblogs.com/grandyang/p/4315649.html 解法4
class Solution:
def grayCode(self, n: int) -> List[int]:
res = [0]
used = set(res)
mask = [1<<i for i in range(n)]
self.dfs(res, used, n, mask)
return res
def dfs(self, res, used, n, mask):
if len(res) == 1<<n:
return True
for m in mask:
then = m^res[-1]
if then in used:
continue
used.add(then)
res.append(then)
if self.dfs(res, used, n, mask):
return True
res.pop()
used.remove(then)
sample 28 ms submission:
class Solution:
def grayCode(self, n: int) -> List[int]:
ans = []
def recur(i, num):
if i == n:
ans.append(num[0])
return
recur(i + 1, num)
num[0] = num[0] ^ (1 << n - i - 1)
recur(i + 1, num)
recur(0, [0])
return ans
sample 24 ms submission: https://www.cnblogs.com/grandyang/p/4315649.html 解法2
class Solution:
def grayCode(self, n: int) -> List[int]:
res = [0]
for i in range(n):
res += [x|(1<<i) for x in res[::-1]]
return res
Calculate according to the attribution of Gray code: https://www.cnblogs.com/grandyang/p/4315649.html 解法1
unsigned int binaryToGray(unsigned int num)
{
return (num >> 1) ^ num;
}
print([bin((x>>1)^x) for x in range(8)])
# ['0b0', '0b1', '0b11', '0b10', '0b110', '0b111', '0b101', '0b100']
print([bin((x>>1)^x)[2:].zfill(3) for x in range(8)])
# ['000', '001', '011', '010', '110', '111', '101', '100']
Python Bitwise Operators:
- x << y
Returns x with the bits shifted to the left by y places (and new bits on the right-hand-side are zeros). This is the same as multiplying x by 2**y.- x >> y
Returns x with the bits shifted to the right by y places. This is the same as //'ing x by 2**y.- x & y
Does a "bitwise and". Each bit of the output is 1 if the corresponding bit of x AND of y is 1, otherwise it's 0.- x | y
Does a "bitwise or". Each bit of the output is 0 if the corresponding bit of x AND of y is 0, otherwise it's 1.- ~ x
Returns the complement of x - the number you get by switching each 1 for a 0 and each 0 for a 1. This is the same as -x - 1.- x ^ y
Does a "bitwise exclusive or". Each bit of the output is the same as the corresponding bit in x if that bit in y is 0, and it's the complement of the bit in x if that bit in y is 1.
