Share my 5 lines Code in Python, based on observation


  • 0
    M
    class Solution:
        # @param {integer} n
        # @return {integer[]}
        def grayCode(self, n):
            
            # set the result as [0] when n = 0
            result = [0]
            
            # based on obervation
            # n = 0, [0]
            # n = 1, [0, 1]
            # n = 2, [0, 1, 3, 2]
            # n = 3, [0, 1, 3, 2, 6, 4, 7, 5]
            # each time just append the original list with the revesed list and add 2 ** (n-1)
            for i in range(n):
                for j in range(2 ** i):
                    result.append(result[2 ** i - j - 1] + 2 ** i)
            return result

  • 0
    G

    I used the same approach as you, but with recursion:

    class Solution(object):
        def grayCode(self, n):
            """
            :type n: int
            :rtype: List[int]
            """
            if n < 1:
                return [0]
            if n == 1:
                return [0, 1]
            
            m = 1 << (n - 1)
            seq = self.grayCode(n - 1)
            for i in reversed(seq):
                seq.append(m | i)
            
            return seq

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.