leetcode 89. 格雷编码 Gray Code

目录

1. 搜索
2. 镜像法
3. 公式法

https://leetcode-cn.com/problems/gray-code/

我自己写的是第一种方法，又总结了题解中看到的两种方法

搜索

class Solution:
    def grayCode(self, n: int) -> List[int]:
        f = [False] * (2 ** n)
        f[0] = True
        r = [0]
        def dfs(x):
            if len(r) == 2 ** n: return
            cur = 1
            for i in range(n):
                if x & cur:
                    if not f[x-cur]:
                        f[x-cur] = True
                        r.append(x-cur)
                        dfs(x-cur)
                        return
                else:
                    if not f[x|cur]:
                        f[x|cur] = True
                        r.append(x|cur)
                        dfs(x|cur)
                        return
                cur <<= 1
        dfs(0)
        return r

镜像法

出自题解 https://leetcode-cn.com/problems/gray-code/solution/gray-code-jing-xiang-fan-she-fa-by-jyd/

n + 1 的答案是 n 的答案复制两份，一上一下拼起来，上面的最高位补 0 （实际上就是不变）下面最高为补 1，并倒序。

class Solution:
    def grayCode(self, n: int) -> List[int]:
        if n == 0:
            return [0]
        if n == 1:
            return [0, 1]
        r = self.grayCode(n-1)
        return r + [r[i] + (1<<n-1)   for i in range(len(r)-1,-1,-1)]

公式法

这个就更强了，方法出自 https://leetcode-cn.com/problems/gray-code/solution/ge-lei-ma-shu-xue-xing-zhi-by-world-16/

直接根据公式算出来了：

gray_code\[i\] = (i >> 1) ^ i

class Solution:
    def grayCode(self, n: int) -> List[int]:
        return [(i>>1)^i for i in range(2**n)]