One-liner Python solution (with demo in comments)


  • 36
    B

    All you need is a bit of careful thought.

    Btw, it's extremely useful to write down your thought/demo in comments before you actually start to write the code, especially during interview.

    Even if you do not solve the problem finally, the interviewer at least get to know what you're thinking.

    And if you don't get the problem right, he/she will have a chance to correct you.

    class Solution:
        # @return a list of integers
        '''
        from up to down, then left to right
        
        0   1   11  110
                10  111
                    101
                    100
                    
        start:      [0]
        i = 0:      [0, 1]
        i = 1:      [0, 1, 3, 2]
        i = 2:      [0, 1, 3, 2, 6, 7, 5, 4]
        '''
        def grayCode(self, n):
            results = [0]
            for i in range(n):
                results += [x + pow(2, i) for x in reversed(results)]
            return results

  • 0
    H

    Finally get the way to solve the problem .
    3Q.


  • 0
    T

    best explanation I found so far! thank you!


  • 0
    D

    nice solution !you rock~


  • 0
    S

    what is the time complexity?


  • 0
    L

    @byronyi O(n*(n+m)) vs O(2^x) solution where x can only go up to 31, because of this a O(2^x) is faster

    I would do something like this instead:

    def grayCode(self, n):
        if n == 0:
            return [0] 
        nMax = 2**n
        return [(x>>1)^x for x in range(nMax)]

  • 1

    Same idea but slightly different implementation.

    class Solution(object):
        def grayCode(self, n):
            res = [0]
            for i in range(n):
                res += [x|(1<<i) for x in res[::-1]]
            return res
    

  • 0
    P

    So nice solution, you rock me. Thank you!


  • 0
    W

    better to use | than +

    results += [x | (1 << i) for x in reversed(results)]
    

  • 0

    I implemented the same thing but just some comments to help if someone cannot understand the logic clearly.

    We just wrote down the pattern of the solution:

    start: [0]
    i = 0:          [0]
    i = 1:          [0, 1]
                      nums[1] = nums[0] + 1
    i = 2:          [0, 1, 3, 2]
                      nums[2:4] = nums[1: : -1] + 2
    i = 3:          [0, 1, 3, 2, 6, 7, 5 ,4]
                     nums[4:8] = nums[3:: -1] + 4
    similarly, we have nums[2**(i-1):2**i] =  nums[2**(i-1)-1::-1] + 2**(i-1)

Log in to reply
 

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