Leetcode算法条记-（全分列I、全分列II、N皇后）

1. 全分列I

题目：给定一个不含重复数字的数组 nums ，返回其 所有可能的全分列 。你可以按恣意次序返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
思绪：参考Krahets大神
着实就是高中学的分列组合，对于一个长度为 n 的数组（假设元素互不重复），其分列方案数共有：n! = n×(n−1)×(n−2)…×2×1
根据数组分列的特点，思量深度优先搜索所有分列方案。即通过元素交换，先固定第 1 位元素（ n 种情况）、再固定第 2 位元素（ n−1 种情况）、... 、末了固定第 n 位元素（ 1 种情况）。

递归终止条件：
当x = len(nums) – 1时，
x是nums的位置，只要到nums的末了一个位置就停止，（nums范围是[0, len(nums) - 1],末了一位只有1种情况），将当前组合nums转化为数组并添加到res中，并返回（注意返回到哪里去）。

1. from typing import List
3. class Solution:
5.     def permute(self, nums: List[int]) -> List[List[int]]:
7.         def dfs(x):
9.             if x == len(nums) - 1:
11.                 res.append(list(nums))   #将 nums 的副本添加到 res
13.                 # res.append(nums.copy()) 也可以
15.                 return
17.             for i in range(x, len(nums)):
19.                 nums[i], nums[x] = nums[x], nums[i]  # 交换，将 nums[i] 固定在第 x 位
21.                 dfs(x + 1)   # 开启固定第 x + 1 位元素
23.                 nums[i], nums[x] = nums[x], nums[i]  # 恢复交换
25.         res = []
27.         dfs(0)
29.         return res

复制代码

时间复杂度 O(n !n) ： n 为数组 nums 的长度；时间复杂度和数组分列的方案数成线性关系，方案数为 n×(n −1)×(n −2)…×2×1 ，即复杂度为 O(n!) ；必要将当前答案使用 O(n) 的时间复制到答案数组中，相乘得时间复杂度为 O(n×n!) 。
空间复杂度 O(n) ： 全分列的递归深度为 n ，系统累计使用栈空间巨细为 O(n)
打印效果

1. nums = [1,2,3]
3. result = Solution()
5. output = result.permute(nums)
7. print(output)

复制代码

看不懂递归过程可以参考下图进行单步调试，记住原来nums里是什么，递归后是什么。

2. 全分列II

题目：
给定一个可包含重复数字的序列 nums ，按恣意次序 返回所有不重复的全分列
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2], [1,2,1], [2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
思绪：参考Krahets大神
与上一题全分列I的区别是数组中“存在重复元素”。当数组存在重复元素时，分列方案中也存在重复的分列方案。为了清除这些重复方案，需在固定某位元素时，包管“每种元素只在此位固定一次”，即遇到重复元素时不交换，直接跳过，从而将生成重复分列的搜索分支进行“剪枝” 。

1. from typing import List
2. class Solution:
3.     def permute(self, nums:List[int]) -> List[List[int]]:
4.         def dfs(x):
5.             if x == len(nums) - 1:
6.                 res.append(nums.copy())
7.                 # res.append(list(nums)) 也可以
8.                 return
9.             dic = set()
10.             for i in range(x, len(nums)):
11.                 if nums[i] in dic: continue
12.                 dic.add(nums[i])
13.                 nums[i], nums[x] = nums[x], nums[i]
14.                 dfs(x+1)
15.                 nums[x], nums[i] = nums[i], nums[x]
16.         res = []
17.         dfs(0)
18.         return res

复制代码

打印效果

1. nums = [1, 1, 2]
2. result = Solution()
3. output = result.permute(nums)
4. print(output)

复制代码

时间复杂度 O(n !n) ： 与上一题相同 。
空间复杂度 O(n2 ) ： 递归中辅助 Set 累计存储的元素数量最多为 n +( n −1)+...+2+1=( n +1) n /2 ，因此占用 O(n2) 的额外空间。
3. N皇后

题目：
给你一个整数 n ，返回所有不同的 n 皇后问题 的办理方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例1：

示例 2：
输入：n = 1
输出：[["Q"]]
思绪：参考灵神
枚举列号的全分列
可以参考下面图明白

Note：
（1）递归终止条件：所有行都放置了皇后   if r == n:
（2）return 是返回到上一个放置皇后的位置，就是图中上一行的红圈位置
注意这里与全分列终止条件：
全分列中，x是nums的位置，只要到nums的末了一个位置就停止
x == len(nums) - 1时候，nums的位置已经交换完了
但是N皇后中，if r == n:是r刚到第三行，还没完全放完，当r = 4时，才放完第3行
举个栗子（N皇后中）：
假设 n=4，行号为 0, 1, 2, 3。
情况1：if r == n
当 r=4 时，表示已经处置惩罚完所有行（0, 1, 2, 3），所有皇后都已放置完毕。
此时生成棋盘设置并存入 ans。
情况2：if r == n - 1
当 r=3 时，表示正在处置惩罚末了一行（第 3 行），但尚未放置皇后。
如果此时终止递归，会导致末了一行未被处置惩罚，无法生成完整的棋盘设置。

1. from typing import List
2. class Solution:
3.     def solveNQueens(self, n: int) -> List[List[str]]:
4.         ans = []
5.         queens = [0] * n  # 皇后放在 (r, queens[r]), # 记录每行皇后的列位置（queens[r] = c）
6.         col = [False] * n
7.         diag1 = [False] * (2 * n - 1)
8.         diag2 = [False] * (2 * n - 1)
10.         def dfs(r: int) -> None:
11.             # 递归终止条件：所有行都放置了皇后
12.             if r == n:
13.                 ans.append(['.' * c + 'Q' + '.' * (n - 1 - c) for c in queens])
14.                 return
15.             """尝试在当前行(r)的每一列放置皇后"""
16.             for c in range(n):
17.                 # 检查当前列和对角线是否被占用
18.                 if not col[c] and not diag1[r + c] and not diag2[r - c]:
19.                     # 放置皇后并标记
20.                     queens[r] = c
21.                     col[c] = diag1[r + c] = diag2[r - c] = True
22.                     # 递归处理下一行
23.                     dfs(r + 1)
24.                     col[c] = diag1[r + c] = diag2[r - c] = False
25.         dfs(0)  # 从第0行开始递归
26.         return ans

复制代码

打印效果

1. n = 4
2. result3 = Solution()
3. output3 = result3.solveNQueens(n)
4. print(output3)

复制代码

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。