LeetCode 89. 格雷编码（中）

可以同时通过动态规划和回溯算法求解的一道题目

题目

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

示例

示例 1:

1
2
输入: 2
输出: [0, 1, 3, 2]

解释:

1
2
3
4
00 - 0  
01 - 1  
11 - 3  
10 - 2
对于给定的 n，其格雷编码序列并不唯一。
例如，[0,2,3,1] 也是一个有效的格雷编码序列。

1
2
3
4
00 - 0
10 - 2
11 - 3
01 - 1

示例 2:

1
2
输入: 0
输出: [0]

解释: 我们定义格雷编码序列必须以 0 开头。
给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。
因此，当 n = 0 时，其格雷编码序列为 [0]。

示例 3:

1
2
输入: 3
输出: [0, 1, 3, 2, 6, 7, 5, 4]

解释

1
2
3
4
5
6
7
8
9
Int Grey Code   Binary   Decimal
    000          000        0
    001          001        1
    011          010        3
    010          011        2
    110          100        6
    111          101        7
    101          110        5
    100          111        4

考察知识点

回溯算法

核心思想

方法一、根据格雷数镜面排列性质求解（可以理解成动态规划）

直觉
1、先翻转 0 1，得到长度为 n 的排列 0 1 1 0 （n=4）。
2、在前 n/2 个数字不变，在后 n/2 个排列前加 1。组成新排列，以此类推。

250px-Binary-reflected_Gray_code_construction.svg.png

代码

  • 声明初始 res=[0]。
  • 开始外层循环，由 n 控制镜面排列重复次数。
    • 开始内层循环，由 len(res) 控制新增数字个数，例如 n=1 时，res=[0, 1]，则 n=2 时，要新增 2 个数字，内层循环进行两次。
      • 内层循环关键逻辑 res.append(res[j] | (1 << i)) ，其中 res[j] 是复制，(1 << i) 是新增n/2 个数字前面的要添加的 1，左移相应位置之后，通过或运算 |，添加上去。

运算过程

1
2
3
4
n = 1  res = [0] + (0 | 1 << 0) = [0, 1]  # a | b |为或运算，只要a、b中有一个为1即可。
n = 2  res = [0, 1] + (1 | 1 << 1) + (0 | 1 << 1) = [0, 1, 3, 2]
n = 3  res = [0, 1, 3, 2] + (2 | 1 << 2) + (3 | 1 << 2) + (1 | 1 <<3) + (0 | 1 <<3) = [0, 1, 3, 2, 6, 7, 4, 3]
# 3 | 1 << 2 = 3 + 2**2 = 3 + 4 = 7

这个解法也可以理解成动态规划，状态转移方程就是：

1
dp += dp[j] | 1 << i

方法二、直接将二进制数字转成格雷码

由维基百科可知 二进制数字 和 格雷码 之间的转换公式是： \[ gray\_num = binary\_num >> 1\ \wedge\ binary\_num \] 由此可循环 \(2^n\) 个数字，依次处理即可。

方法三、回溯算法

回溯算法算法模板

1
2
3
4
5
6
7
8
9
result = []
def backtrack(路径, 选择列表):  # 选择列表是由一系列参数组成的
    if 满足结束条件:
        result.add(路径)  # 路径就是要添加的结果
        return
    for 选择 in 选择列表: / if 选择条件:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

0c3c0ec972d14147114298bf7c280199b5786de7774669c04ea5fd40062bdbc7-image.png

从空字符串开始，上面的（绿色）分别加0、1，下面的（红色）分别加1、0，直到长度达n。
所以回溯的终止条件是 len(path) == n
选择列表通过一个 flag 变量判断当前到底是加 0 还是加 1。

Python版本

  • 方法一根据格雷数镜面排列性质的实现
1
2
3
4
5
6
7
8
9
class Solution:
    def grayCode(self, n: int) -> List[int]:
        res = [0]
        for i in range(n):
            size = len(res)
            # 为啥要从后面往前循环，因为是镜像的，由0 1得到1 0，所以必须从后往前循环。
            for j in range(size-1, -1, -1):  
                res.append(res[j] | (1 << i))
        return res

时间复杂度：\(O(2^n)\)

  • 方法二直接将二进制数字转成格雷码的实现
1
2
3
4
5
6
class Solution:
    def grayCode(self, n: int) -> List[int]:
        res = []
        for i in range(2**n):
            res.append((i >> 1)^i)
        return res

空间复杂度：\(O(2^n)\)

  • 方法三回溯算法的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def grayCode(self, n: int) -> List[int]:
        def backtrack(path, flag):
            if len(path) == n:
                res.append(int(path, 2))
                return
            if flag == 0:  # 上面的（绿色）分别加0、1
                backtrack(path + "0", 0)
                backtrack(path + "1", 1)
            else:  # （红色）分别加1、0
                backtrack(path + "1", 0)
                backtrack(path + "0", 1)
        if n == 0:  return [0]
        res = []
        backtrack("", 0)
        return res

Input = [3, 2, 1, 0]
Answer = [[0, 1, 3, 2, 6, 7, 5, 4], [0, 1], [0, 1, 3, 2], [0]]
if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)): 
        print("-"*50)
        result = solution.grayCode(Input[i])
        print(result == Answer[i])

时间复杂度为：\(O(2^n)\)

参考链接

力扣（LeetCode）dannnn
Grandyang