qidao123.com技术社区-IT企服评测·应用市场

标题: Leetcode算法条记-（全分列I、全分列II、N皇后） [打印本页]
作者: 花瓣小跑    时间: 5 天前
标题: 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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/) Powered by Discuz! X3.4