灵神基础算法精讲-16-学习笔记

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

思路

数组元素各不相同，那么全排列的个数就是数组长度的阶乘。

相比组合，在排列中，元素的顺序是有区别的。

用一个数组 $path$ 记录路径上的数字（已选数字）。
集合 $s$ 记录剩余未选数字。

回溯三问：

1. 当前操作：从 $s$ 中枚举 $path[i]$ 要填入的数字 $x$。
2. 子问题：构造排列大于等于 $i$ 的部分，剩余未选数字集合为 $s$。
3. 下一个子问题：构造排列大于等于 $i+1$ 的部分，剩余未选数字集合为 $s-{x}$。

做法1（哈希表）

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # 1. 每个位置都要填一个数
        # 2. 每个位置填的数互不相同
        n = len(nums)
        ans = []
        path = [0] * n
        def dfs(i: int, s: Set[int]) -> None:
            if i == n:
                ans.append(path.copy())
                return
            for x in s:
                path[i] = x
                dfs(i + 1, s - {x})
        dfs(0, set(nums))
        return ans

时间复杂度：O(n*n!)。
空间复杂度：O(n)。

只要是分叉大于等于 2 的树的部分，有：非叶子节点数 < 叶子节点数，所以时间复杂度可以只看叶子节点数，即 O(n!)。

做法2（布尔数组）

用一个布尔数组 $onPath$ 记录在 $path$ 中的数字，如果 nums[i] 在 $path$ 中，则 $onPath[i]$ 为真。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        path = [0] * n  # 所有排列的长度都是一样的 n
        on_path = [False] * n
        def dfs(i: int) -> None:
            if i == n:
                ans.append(path.copy())  # 也可以写 path[:]
                return
            for j, on in enumerate(on_path):
                if not on:
                    path[i] = nums[j]  # 从没有选的数字中选一个
                    on_path[j] = True  # 已选上
                    dfs(i + 1)
                    on_path[j] = False  # 恢复现场
                    # 注意 path 无需恢复现场，因为排列长度固定，直接覆盖就行
        dfs(0)
        return ans

51. N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

思路

每行每列恰好有一个皇后，用一个长为 n 的数组 $col$ 记录皇后的位置，即第 i 行的皇后在第 $col[i]$ 列。那么 $col$ 必须是一个 0 到 n - 1 的排列。

示例1左图 $col = [1, 3, 0, 2]$，右图 $col = [2, 0, 3, 1]$。

还有一个要求是皇后不能在同一斜线上。由于是从上到下枚举的，那么只需要看右上和左上这两个方向有没有皇后。对于右上方向的皇后，在这条线上行号 + 列号是不变的，即 r + c 是一个定值；对于左上方向同理，在这条线上行号 - 列号是不变的，即 r - c 是一个定值。

做法1

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        ans = []
        col = [0] * n

        def valid(r, c):
            for R in range(r):
                C = col[R]
                if r+c == R+C or r-c == R-C:
                    return False
            return True

        def dfs(r, s):
            if r == n:
                ans.append(['.'*c + 'Q' + '.'*(n-1-c) for c in col])
                return
            for c in s:
                if valid(r, c):
                    col[r] = c
                    dfs(r+1, s-{c})
        dfs(0, set(range(n)))
        return ans

时间复杂度：O(n^2*n!)。
空间复杂度：O(n)。

做法2

优化：既然可以用 r + c 和 r - c 判断，那么干脆把 r + c 记录到一个布尔数组 diag1 中，在放皇后前判断，如果 diag1[r+c] 为真，则无法放皇后。

对于 r - c 同理，用布尔数组 diag2 记录，为了避免负数需要加上 n - 1。

这样优化后，判断能否放皇后的时间复杂度就从 O(n) 降为 O(1)。

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        ans = []
        queens = [0] * n  # 皇后放在 (r,queens[r])
        col = [False] * n
        diag1 = [False] * (n * 2 - 1)
        diag2 = [False] * (n * 2 - 1)
        def dfs(r: int) -> None:
            if r == n:
                ans.append(['.' * c + 'Q' + '.' * (n - 1 - c) for c in queens])
                return
            # 在 (r,c) 放皇后
            for c, ok in enumerate(col):
                if not ok and not diag1[r + c] and not diag2[r - c]:  # 判断能否放皇后
                    queens[r] = c  # 直接覆盖，无需恢复现场
                    col[c] = diag1[r + c] = diag2[r - c] = True  # 皇后占用了 c 列和两条斜线
                    dfs(r + 1)
                    col[c] = diag1[r + c] = diag2[r - c] = False  # 恢复现场
        dfs(0)
        return ans

时间复杂度：与做法1相同，时间复杂度瓶颈在构造答案，O(n^2*n!)。
空间复杂度：O(n)。