Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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))
linkedin
github
slack

Post Views: 7
Posted in MediumTagged #dynamicprogramming, #game, baseconversion

Post navigation

LeetCode: Sparse Matrix Multiplication
LintCode: 3Sum II

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.