这周一道算法题(六十五)

本周题目难度级别'Medium'，使用语言Python

题目：给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。eg：给定n为2，则return [0,1,3,2]

思路：我做这题光弄懂格雷码就花了好久的时间，然后就是写出来找规律了：

• n = 0: [0]
• n = 1: [0, 1]
• n = 2: [0, 1, 3, 2]
• n = 3: [0, 1, 3, 2, 6, 7, 5, 4]
• n = 4: [0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]...

可以发现n=1的时候，其实就是[0]再拼接上把[0]倒过来(逆序)的每个数加上2⁰
当n=2的时候，就是[0,1]再拼接上把[0,1]倒过来(逆序)的每个数加上2¹
...
即n就是n-1的列表拼接上把n-1列表倒过来(逆序)的每个数加上2^n-1
大功告成，下面看下实现思路的代码：

class Solution:
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        result = [0]
        for i in range(0, n):
            # result[::-1]将列表的数倒过来(逆序)，并且每个数加上2的i次方后，拼接到result的后面
            result += [(pow(2, i) + x) for x in result[::-1]]
        return result

代码虽然简单，效率一般，看下大神的高效简洁代码，只要一行，我不加注释了：

class Solution:
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        return [i ^ (i >> 1) for i in range(1 << n)]

简单解释一下^,<<,>>这三个运算符：
a ^ b:a的二进制数与b的二进制数的每一位相等的为0，不相等的为1。即00与11为0，01与10为1
a << b:a的二进制数左移b位，相当于a除以2的b次方取整
a >> b:a的二进制数右移b位，相当于a乘以2的b次方

---

做完题再送一个生成二进制的代码（当然也可以把上面的代码改一下，转成二进制即可）：

def grayCodeBinary(n):
    if not n: return ['0']
    else:
        result = ['0', '1']
        for k in range(1, n):
            # 前半部分加前缀0
            before = ['0' + i for i in result]
            # 后半部分加前缀1
            after  = ['1' + i for i in result[::-1]]
            # 合起来即可
            result = before + after
        return result

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!