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.
A valid gray code sequence of length
n can be generated by prepending
0 to the gray code sequence of length
n - 1 in order, followed by prepending
1 to the gray code sequence of length
n - 1 in reverse order.
class Solution: def grayCode(self, n): """ :type n: int :rtype: List[int] """ if n == 0: return  elif n == 1: return[0, 1] else: results = self.grayCode(n - 1) length = len(results) leading_bit = 2 ** (n - 1) for i in range(length - 1, -1, -1): results.append(leading_bit + results[i]) return results