LeetCode: Gray Code Posted on March 2, 2018July 26, 2020 by braindenny Gray Code Similar Problems: Lexicographical Numbers CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #dynamicprogramming, #baseconversion, #game 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. Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. ## https://code.dennyzhang.com/gray-code class Solution: def grayCode(self, n): """ :type n: int :rtype: List[int] """ res = [0] for i in range(n): v = pow(2, i) for j in range(len(res)-1, -1, -1): res.append(res[j]+v) return res ## Basic Ideas: dynamic programming ## get f(n) from f(n-1) ## copy the original ## add pow(2, n-1) to each item from right to left ## ## from f(2) to f(3) ## 00 01 11 10 ## 00 01 11 10 110 111 101 100 ## Complexity: def grayCode_v1(self, n): """ :type n: int :rtype: List[int] """ if n <= 0: return [0] if n == 1: return [0, 1] import copy l = [0, 1] for i in range(2, n+1): l2 = copy.deepcopy(l) v = pow(2, i-1) for k in range(len(l)-1, -1, -1): l2.append(v+l[k]) l = l2 return l # s = Solution() # print(s.grayCode(2)) # print(s.grayCode(3)) Post Views: 7