Leetcode算法条记-(全分列I、全分列II、N皇后)

打印 上一主题 下一主题

主题 2033|帖子 2033|积分 6099

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
  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(list(nums))   #将 nums 的副本添加到 res
  7.                 # res.append(nums.copy()) 也可以
  8.                 return
  9.             for i in range(x, len(nums)):
  10.                 nums[i], nums[x] = nums[x], nums[i]  # 交换,将 nums[i] 固定在第 x 位
  11.                 dfs(x + 1)   # 开启固定第 x + 1 位元素
  12.                 nums[i], nums[x] = nums[x], nums[i]  # 恢复交换
  13.         res = []
  14.         dfs(0)
  15.         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]
  2. result = Solution()
  3. output = result.permute(nums)
  4. 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)
  9.         def dfs(r: int) -> None:
  10.             # 递归终止条件:所有行都放置了皇后
  11.             if r == n:
  12.                 ans.append(['.' * c + 'Q' + '.' * (n - 1 - c) for c in queens])
  13.                 return
  14.             """尝试在当前行(r)的每一列放置皇后"""
  15.             for c in range(n):
  16.                 # 检查当前列和对角线是否被占用
  17.                 if not col[c] and not diag1[r + c] and not diag2[r - c]:
  18.                     # 放置皇后并标记
  19.                     queens[r] = c
  20.                     col[c] = diag1[r + c] = diag2[r - c] = True
  21.                     # 递归处理下一行
  22.                     dfs(r + 1)
  23.                     col[c] = diag1[r + c] = diag2[r - c] = False
  24.         dfs(0)  # 从第0行开始递归
  25.         return ans
复制代码
打印效果
  1. n = 4
  2. result3 = Solution()
  3. output3 = result3.solveNQueens(n)
  4. print(output3)
复制代码

 

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

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?立即注册

x
回复

使用道具 举报

0 个回复

倒序浏览

快速回复

您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

花瓣小跑

论坛元老
这个人很懒什么都没写!
快速回复 返回顶部 返回列表