数据结构与算法一回溯
目录
数据结构与算法（一）回溯
数据结构与算法（一）回溯(backtrack)
回溯算法是对树形或者图形结构执行一次深度优先遍历，实际上类似枚举的搜索尝试过程，在遍历的过程中寻找问题的解。
- 深度优先遍历有个特点：当发现已不满足求解条件时，就返回，尝试别的路径。此时对象类型变量就需要重置成为和之前一样，称为「状态重置」。
- 许多复杂的，规模较大的问题都可以使用回溯法，有「通用解题方法」的美称。实际上，回溯算法就是暴力搜索算法，它是早期的人工智能里使用的算法，借助计算机强大的计算能力帮助我们找到问题的解。
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就 “回溯” 返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，
这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为 “回溯点”。
许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
- 回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
回溯的思路
回溯的思路:
1.有效结果：什么时候这算是一个答案，应该被加入到答案列表里
2.回溯的范围：我们下一个维度要考虑如何将当前层的答案和上一层的答案结合，并继续递归
3.剪枝条件：是不是存在某些情况遇到了之后就不需要再处理了
解决一个回溯问题，实际上就是一个决策树的遍历过程。
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。
对于以上几个问题，我们需要以下几个变量
1 self.res: 用来保存全部的答案，即整体的答案列表; sol: 每一次的有效结果，某一个符合条件的答案
2.1 回溯范围需要是全部遍历，还是部分范围遍历 2.2 答案如何累加
3 check：这是一个list，初始为0，当某个元素被用过，则改为1，这是因为在回溯里面主要的思路是搜索尝试过程中寻找问题的解，
当发现已不满足求解条件时，就“回溯”返回，尝试别的路径, 那么就需要一个数组来记录用过的元素，避免陷入死循环
总结
回溯类题一定要考虑的几个方面
- 有效结果：当长度为输入长度的时候停止，并保存当前结果
- 回溯条件：每一层都是全部元素遍历：例如答案为[2,1,3]时，第二个元素也是从1开始
- 剪枝条件：要用check数组来保存用过的元素，用过的不能再用了，这是回溯里面的一个重要考虑因素
代码方面，回溯算法的框架：
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
作者：labuladong
链接：https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-xiang-jie-by-labuladong-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。经典题目
leetcode经典题目
回溯算法力扣题目总结
组合问题
77.组合
216.组合总和III
17.电话号码的字母组合
39.组合总和
40.组合总和II
分割问题
131.分割回文串
93.复原IP地址
子集问题
78.子集
90.子集II
排列问题
46.全排列
47.全排列II
棋盘问题
51.N皇后
37.解数独
其他
491.递增子序列
332.重新安排行程
回溯算法总结篇
作者：carlsun-2
链接：https://leetcode-cn.com/problems/combination-sum/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-hui-s-7tum/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
题型一：排列、组合、子集相关问题
提示：这部分练习可以帮助我们熟悉「回溯算法」的一些概念和通用的解题思路。解题的步骤是：先画图，再编码。去思考可以剪枝的条件， 为什么有的时候用 used 数组，有的时候设置搜索起点 begin 变量，理解状态变量设计的想法。
46. 全排列（中等）
47. 全排列 II（中等）：思考为什么造成了重复，如何在搜索之前就判断这一支会产生重复；
39. 组合总和（中等）
40. 组合总和 II（中等）
77. 组合（中等）
78. 子集（中等）
90. 子集 II（中等）：剪枝技巧同 47 题、39 题、40 题；
60. 第 k 个排列（中等）：利用了剪枝的思想，减去了大量枝叶，直接来到需要的叶子结点；
93. 复原 IP 地址（中等）
题型二：Flood Fill
提示：Flood 是「洪水」的意思，Flood Fill 直译是「泛洪填充」的意思，体现了洪水能够从一点开始，迅速填满当前位置附近的地势低的区域。类似的应用还有：PS 软件中的「点一下把这一片区域的颜色都替换掉」，扫雷游戏「点一下打开一大片没有雷的区域」。
下面这几个问题，思想不难，但是初学的时候代码很不容易写对，并且也很难调试。我们的建议是多写几遍，忘记了就再写一次，参考规范的编写实现（设置 visited 数组，设置方向数组，抽取私有方法），把代码写对。
733. 图像渲染（Flood Fill，中等）
200. 岛屿数量（中等）
130. 被围绕的区域（中等）
79. 单词搜索（中等）
说明：以上问题都不建议修改输入数据，设置 visited 数组是标准的做法。可能会遇到参数很多，是不是都可以写成成员变量的问题，面试中拿不准的记得问一下面试官
题型三：字符串中的回溯问题
提示：字符串的问题的特殊之处在于，字符串的拼接生成新对象，因此在这一类问题上没有显示「回溯」的过程，但是如果使用 StringBuilder 拼接字符串就另当别论。
在这里把它们单独作为一个题型，是希望朋友们能够注意到这个非常细节的地方。
17. 电话号码的字母组合（中等），题解；
784. 字母大小写全排列（中等）；
22. 括号生成（中等） ：这道题广度优先遍历也很好写，可以通过这个问题理解一下为什么回溯算法都是深度优先遍历，并且都用递归来写。
题型四：游戏问题
回溯算法是早期简单的人工智能，有些教程把回溯叫做暴力搜索，但回溯没有那么暴力，回溯是有方向地搜索。「力扣」上有一些简单的游戏类问题，解决它们有一定的难度，大家可以尝试一下。
51. N 皇后（困难）：其实就是全排列问题，注意设计清楚状态变量，在遍历的时候需要记住一些信息，空间换时间；
37. 解数独（困难）：思路同「N 皇后问题」；
488. 祖玛游戏（困难）
529. 扫雷游戏（困难）
（欢迎大家补充。）
作者：liweiwei1419
链接：https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。参考
详细说明
目录
- [六、泛洪填充(Flood Fill)](#六、泛洪填充(Flood Fill))
一、组合问题
39. Combination Sum
- 组合总和
"""
39. 组合总和
给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
示例 1：
输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
示例 4：
输入: candidates = [1], target = 1
输出: [[1]]
示例 5：
输入: candidates = [1], target = 2
输出: [[1,1]]
提示：
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500
通过次数333,988提交次数459,064
"""
from typing import List
class Solution:
""" 回溯, 重点是sort排序后避免重复, 可设置begin避免重复(裁剪) """
def combinationSum_my00(self, candidates: List[int], target: int) -> List[List[int]]:
if not candidates:
return []
def backtrack(candidates, target, path):
if target == 0:
path.sort()
if path not in output:
output.append(path)
return
for i in range(len(candidates)):
cand_enum = candidates[i]
if target-cand_enum >= 0:
# candidates.remove(cand_enum)
# visited[i] = 1
backtrack(candidates, target-cand_enum, path+[cand_enum])
# visited[i] = 0
# candidates.append(cand_enum)
output = []
# visited = [0 for c in range(len(candidates))]
backtrack(candidates, target, [])
return output
"""
以 target = 7 为 根结点 ，创建一个分支的时 做减法 ；
每一个箭头表示：从父亲结点的数值减去边上的数值，得到孩子结点的数值。边的值就是题目中给出的 candidate 数组的每个元素的值；
减到 00 或者负数的时候停止，即：结点 00 和负数结点成为叶子结点；
所有从根结点到结点 00 的路径（只能从上往下，没有回路）就是题目要找的一个结果。
作者：liweiwei1419
链接：https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def combinationSum_hot_1(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(candidates, begin, size, path, res, target):
if target < 0:
return
if target == 0:
res.append(path)
return
for index in range(begin, size):
dfs(candidates, index, size, path + [candidates[index]], res, target - candidates[index])
size = len(candidates)
if size == 0:
return []
path = []
res = []
dfs(candidates, 0, size, path, res, target)
return res
"""
剪枝提速(排序)
根据上面画树形图的经验，如果 target 减去一个数得到负数，那么减去一个更大的树依然是负数，同样搜索不到结果。
基于这个想法，我们可以对输入数组进行排序，添加相关逻辑达到进一步剪枝的目的；
排序是为了提高搜索速度，对于解决这个问题来说非必要。但是搜索问题一般复杂度较高，能剪枝就尽量剪枝。
实际工作中如果遇到两种方案拿捏不准的情况，都试一下。
作者：liweiwei1419
链接：https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def combinationSum_hot_2(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(candidates, begin, size, path, res, target):
if target == 0:
res.append(path)
return
for index in range(begin, size):
residue = target - candidates[index]
if residue < 0:
break
dfs(candidates, index, size, path + [candidates[index]], res, residue)
size = len(candidates)
if size == 0:
return []
candidates.sort()
path = []
res = []
dfs(candidates, 0, size, path, res, target)
return res
"""
有些朋友可能会疑惑什么时候使用 used 数组，什么时候使用 begin 变量。这里为大家简单总结一下：
排列问题，讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时），需要记录哪些数字已经使用过，此时用 used 数组；
组合问题，不讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时），需要按照某种顺序搜索，此时使用 begin 变量。
注意：具体问题应该具体分析， 理解算法的设计思想 是至关重要的，请不要死记硬背。
作者：liweiwei1419
链接：https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
if __name__ == "__main__":
sol = Solution()
candidates = [2, 3, 5]
target = 8
res = sol.combinationSum_my00(candidates, target)
print(res)
gg = 0
"""
回溯就是一个树形、矩形搜索的过程, 画树图.
"""40. Combination Sum II
- 组合总和 II
"""
40. 组合总和 II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
通过次数199,428提交次数319,679
"""
from typing import List
class Solution:
"""
如何去掉重复的集合（重点）
为了使得解集不包含重复的组合。有以下 2 种方案：
1. 使用 哈希表 天然的去重功能，但是编码相对复杂；
2. 这里我们使用和第 39 题和第 15 题（三数之和）类似的思路：不重复就需要按 顺序 搜索， 在搜索的过程中检测分支是否会出现重复结果 。
注意：这里的顺序不仅仅指数组 candidates 有序，还指按照一定顺序搜索结果。
剪枝发生在(从小到大)：同一层数值相同的结点第 2、3 ... 个结点，因为数值相同的第 1 个结点已经搜索出了包含了这个数值的全部结果，
同一层的其它结点，候选数的个数更少，搜索出的结果一定不会比第 1 个结点更多，并且是第 1 个结点的子集。
作者：liweiwei1419
链接：https://leetcode-cn.com/problems/combination-sum-ii/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def combinationSum2_offical_1(self, candidates: List[int], target: int) -> List[List[int]]:
""" 从小到大, 先裁剪再选中, 裁剪要在for循环里边, 即在前面, 递归前面"""
if not candidates or sum(candidates) < target:
return []
if sum(candidates) == target:
return [candidates]
def dfs(begin, path, residue):
print(residue)
print(path[:])
print(res)
if residue == 0:
res.append(path[:])
return
for index in range(begin, size):
if candidates[index] > residue:
break
if index > begin and candidates[index - 1] == candidates[index]:
continue
path.append(candidates[index])
dfs(index + 1, path, residue - candidates[index])
path.pop()
size = len(candidates)
if size == 0:
return []
candidates.sort(reverse=False)
res = []
dfs(0, [], target)
return res
"""哈希表
考虑将相同的数放在一起进行处理，也就是说，如果数 x 出现了 y 次，那么在递归时一次性地处理它们，即分别调用选择 0,1,⋯,y 次 x 的递归函数。
这样我们就不会得到重复的组合。
我们使用一个哈希映射（HashMap）统计数组 candidates 中每个数出现的次数。
在统计完成之后，我们将结果放入一个列表 freq 中，方便后续的递归使用。
列表 freq 的长度即为数组 candidates 中不同数的个数。 其中的每一项对应着哈希映射中的一个键值对，即某个数以及它出现的次数。
在递归时，对于当前的第 pos 个数，它的值为 freq[pos][0]，出现的次数为 freq[pos][1]，那么我们可以调用
dfs(pos+1,rest−i×freq[pos][0])
即我们选择了这个数 i 次。这里 i 不能大于这个数出现的次数，并且 i×freq[pos][0] 也不能大于 rest。
同时，我们需要将 i 个 freq[pos][0] 放入列表中。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/combination-sum-ii/solution/zu-he-zong-he-ii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def combinationSum2_offical_2(self, candidates: List[int], target: int) -> List[List[int]]:
import collections
def dfs(pos: int, rest: int):
nonlocal sequence
if rest == 0:
ans.append(sequence[:])
return
if pos == len(freq) or rest < freq[pos][0]:
return
dfs(pos + 1, rest)
most = min(rest // freq[pos][0], freq[pos][1])
for i in range(1, most + 1):
sequence.append(freq[pos][0])
dfs(pos + 1, rest - i * freq[pos][0]) # 多次-相同的数字
sequence = sequence[:-most]
freq = sorted(collections.Counter(candidates).items())
ans = list()
sequence = list()
dfs(0, target)
return ans
if __name__ == "__main__":
sol = Solution()
# candidates = [2, 3, 5]
# target = 8
# candidates = [10, 1, 2, 2, 7, 6, 1, 5]
# target = 8
# candidates = [10, 1, 2, 7, 6, 1, 5]
# target = 8
# candidates = [2, 5, 2, 1, 2]
# target = 5
# candidates = [10, 1, 2, 7, 6, 1, 5]
# target = 8
# candidates = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
# target = 27
candidates = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
target = 30
print(sum(candidates))
res = sol.combinationSum2_offical_1(candidates, target)
res = sol.combinationSum2_offical_2(candidates, target)
# res = sol.combinationSum2_my00(candidates, target)
print(res)
"""
1.哈希表，考虑将相同的数放在一起进行处理，也就是说，如果数 x 出现了 y 次，那么在递归时一次性地处理它们，即分别调用选择 0,1,⋯,y 次 x 的递归函数。
2.不重复就需要按 顺序 搜索， 在搜索的过程中检测分支是否会出现重复结果 。
"""77. Combinations
- 组合
"""
77. 组合
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
通过次数157,800提交次数205,789
请问您在哪类招聘中遇到此题？
"""
from typing import List, Union, Any
class Solution:
"""
解题思路
算是一道比较经典的回溯题了，首先建立backtrace函数，有两个参数，一个是从1开始一直加到n的整数，一个是暂存的列表。
先用一个if语句判断回溯结束条件，就是列表的长度是否等于k，如果是的话就添加进res中，然后结束递归函数。
如果列表长度小于k的话，就进入循环，将j增大1，且暂存列表加入数字j。
全部结束完输出结果res即可。
作者：luo_luo
链接：https://leetcode-cn.com/problems/combinations/solution/zu-he-python3hui-su-suan-fa-by-luo_luo-d88j/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def combine_2(self, n: int, k: int) -> List[List[int]]:
res = []
def backtrace(i, tmp):
print(tmp)
if len(tmp) == k:
res.append(tmp)
return
for j in range(i, n + 1):
if j > n - (k - len(tmp)) + 1:
break # 剪枝操作，根据此时path中的元素数来舍去不需要考虑的数字
backtrace(j + 1, tmp + [j])
backtrace(1, [])
return res
def combine_3(self, n: int, k: int) -> List[List[int]]:
##先生成数
nums = [i for i in range(1, n + 1)]
# print(nums)
##明显用回溯法:
res = []
def backtrace(nums_b, curr_res, index):
# print("curr_res:",curr_res)
if len(curr_res) == k:
res.append(curr_res[:]) ##浅拷贝，这一步很重要
return
for i in range(index, n):
# print(i,nums_b)
curr_res.append(nums[i])
backtrace(nums_b[index:], curr_res, i + 1)
curr_res.pop()
##特殊情况处理
if n == 0 or k == 0:
return res
backtrace(nums, [], 0)
return res
if __name__ == '__main__':
sol = Solution()
n = 4
k = 2
res = sol.combine_2(n, k)
print(res)
"""
简单回溯, 组合, index, 搜索起点的上界 + 接下来要选择的元素个数 - 1 = n
"""二、排列问题
46. Permutations
- 全排列
"""
46. 全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
通过次数287,181提交次数369,123
"""
from typing import List
class Solution:
""" 方法一：回溯
思路和算法:
这个问题可以看作有 n 个排列成一行的空格，我们需要从左往右依此填入题目给定的 n 个数，每个数只能使用一次。
那么很直接的可以想到一种穷举的算法，即从左往右每一个位置都依此尝试填入一个数，看能不能填完这 nn 个空格，在程序中我们可以用「回溯法」来模拟这个过程。
我们定义递归函数 backtrack(first, output) 表示从左往右填到第 first 个位置，当前排列为 output。 那么整个递归函数分为两个情况：
如果 first==n，说明我们已经填完了 nn 个位置（注意下标从 00 开始），找到了一个可行的解，我们将 output 放入答案数组中，递归结束。
如果 first<n，我们要考虑这第 first 个位置我们要填哪个数。根据题目要求我们肯定不能填已经填过的数，
因此很容易想到的一个处理手段是我们定义一个标记数组 vis[] 来标记已经填过的数，那么在填第 first 个数的时候我们遍历题目给定的 nn 个数，
如果这个数没有被标记过，我们就尝试填入，并将其标记，继续尝试填下一个位置，即调用函数 backtrack(first + 1, output)。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def permute_2(self, nums: List[int]) -> List[List[int]]:
if not nums:
return []
if len(nums) == 1:
return [nums]
ans = []
for i, n in enumerate(nums):
ans.extend([[n] + p for p in self.permute_2(nums[:i] + nums[i + 1:])])
return ans
"""
总结：回溯类题一定要考虑的几个方面
- 有效结果：当长度为输入长度的时候停止，并保存当前结果
- 回溯条件：每一层都是全部元素遍历：例如答案为[2,1,3]时，第二个元素也是从1开始
- 剪枝条件：要用check数组来保存用过的元素，用过的不能再用了，这是回溯里面的一个重要考虑因素
在前面有说在回溯（累加结果）的时候，用如下方式：
check[i] = 1
self.backtrack(sol+[nums[i]], nums, check)
check[i] = 0
其中check的更改是为了在回溯前改变当前使用元素的记录情况，但是在回溯结束之后，调用栈回到上一层，需要将使用元素的状态改回为0，
因为下一个回溯搜索的时候这个元素其实是未使用状态，这样就表明了：在回溯中，修改过的元素在递归调用一层结束之后，都要恢复至原装，
那么意味着我们是sol其实也应该修改回没有添加当前元素的状态
那么sol+[nums[i]]就是一个避免手动更改的小trick，回到上一层的sol其实就是sol，当然我们也可以sol.append(nums[i])，然后在回溯后sol.pop()，
但是要注意list是可变对象，我们在保存结果的时候是self.res.append(sol)，那么在回溯之后的sol.pop()会影响self.res.append(sol)处的sol，
如果要用append+pop处理sol，那么保存结果的时候就必须用self.res.append(sol.copy())
"""
def permute_4(self, nums: List[int]) -> List[List[int]]:
res = []
check = [0 for _ in range(len(nums))]
def backtrack(sol, nums, check):
if len(sol) == len(nums):
res.append(sol)
return
for i in range(len(nums)):
if check[i] == 1:
continue
check[i] = 1
backtrack(sol + [nums[i]], nums, check)
check[i] = 0
backtrack([], nums, check)
return res
if __name__ == '__main__':
sol = Solution()
nums = [1, 2, 3]
res = sol.permute_3(nums)
print(res)
"""
全排列
总结：回溯类题一定要考虑的几个方面
- 有效结果：当长度为输入长度的时候停止，并保存当前结果
- 回溯条件：每一层都是全部元素遍历：例如答案为[2,1,3]时，第二个元素也是从1开始
- 剪枝条件：要用check数组来保存用过的元素，用过的不能再用了，这是回溯里面的一个重要考虑因素
在前面有说在回溯（累加结果）的时候，排列用如下方式：
check[i] = 1
self.backtrack(sol+[nums[i]], nums, check)
check[i] = 0
"""47. Permutations II
- 全排列 II
"""
47. 全排列 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]]
提示：
1 <= nums.length <= 8
-10 <= nums[i] <= 10
通过次数154,817提交次数245,539
"""
from typing import List
class Solution:
"""
回溯问题三要素
把和 46.全排列 的区别--重复，考虑了之后，这道题就是和我们之前写过的思考过程一样了，依然是回到老三样：
1. 有效结果
仍然是当前结果的长度==列表的长度，即为找到了一个有效结果
if len(sol) == len(nums):
self.res.append(sol)
2. 回溯范围及答案更新
仍然是全部遍历，因为每一层都要考虑全部元素
答案更新仍然是在修改 check 之后回溯内部累加更新 sol
for i in range(len(nums)):
check[i] = 1
self.backtrack(sol+[nums[i]], nums, check)
check[i] = 0
3. 剪枝条件
在之前的 剪枝条件1：用过的元素不能再使用之外，又添加了一个新的剪枝条件，也就是我们考虑重复部分思考的结果，于是
剪枝条件2：当当前元素和前一个元素值相同（此处隐含这个元素的 index>0 ），并且前一个元素还没有被使用过的时候，我们要剪枝
if check[i] == 1:
continue
if i > 0 and nums[i] == nums[i-1] and check[i-1] == 0:
continue
"""
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort()
self.res = []
check = [0 for i in range(len(nums))]
def backtrack(sol, nums, check):
if len(sol) == len(nums):
self.res.append(sol)
return
for i in range(len(nums)):
if check[i] == 1:
continue
# 在考虑重复及剪枝条件的时候，我们考虑的是：
# 当当前元素和前一个元素值相同（此处隐含这个元素的index > 0），并且前一个元素还没有被使用过的时候，我们要剪枝
# 但实际，如果条件设为：并且前一个元素被使用过，我们要剪枝，其实也是可以的：
# if i > 0 and nums[i] == nums[i - 1] and check[i - 1] == 1:
# 主要的区别还是在于在那个阶段剪枝，以及重复元素中选择哪一个。
# 结论：选择check[i - 1] == 0 效率要高于check[i - 1] == 1 (提前裁剪)
# 在之前的 剪枝条件1：用过的元素不能再使用之外，又添加了一个新的剪枝条件，也就是我们考虑重复部分思考的结果，于是
# 剪枝条件2：当当前元素和前一个元素值相同（此处隐含这个元素的 index>0 ），并且前一个元素还没有被使用过的时候，我们要剪枝
if i > 0 and nums[i] == nums[i - 1] and check[i - 1] == 0:
continue
check[i] = 1
backtrack(sol + [nums[i]], nums, check)
check[i] = 0
backtrack([], nums, check)
return self.res
if __name__ == '__main__':
sol = Solution()
nums = [3,3,0,3]
res = sol.permuteUnique(nums)
print(res)
"""
回溯问题三要素
把和 46.全排列 的区别--重复，考虑了之后，这道题就是和我们之前写过的思考过程一样了，依然是回到老三样：
1. 有效结果
仍然是当前结果的长度==列表的长度，即为找到了一个有效结果
2. 回溯范围及答案更新
仍然是全部遍历，因为每一层都要考虑全部元素, 答案更新仍然是在修改 check 之后回溯内部累加更新 sol
3. 剪枝条件
剪枝条件1：用过的元素不能再使用之外，又添加了一个新的剪枝条件，也就是我们考虑重复部分思考的结果，于是
剪枝条件2：当当前元素和前一个元素值相同（此处隐含这个元素的 index>0 ），并且前一个元素还没有被使用过的时候，我们要剪枝
"""三、子集问题
78. Subsets
- 子集
"""
78. 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
通过次数238,478提交次数298,885
请问您在哪类招聘中遇到此题？
"""
from typing import List
import itertools
class Solution:
""" 仿照e77, 返回'回溯+k个'的子集 """
def subsets_my00(self, nums: List[int]) -> List[List[int]]:
if not nums:
return []
res = [[], nums]
def dfs(nums, cur, index, k):
if len(cur)==k:
res.append(cur[:])
return
else:
for i in range(index, len(nums)):
cur.append(nums[i])
dfs(nums, cur, i+1, k)
cur.pop()
for i in range(len(nums)):
if i > 0 and i < len(nums):
dfs(nums, [], 0, i)
return res
""" 库函数, python中的工具, itertools """
def subsets_1(self, nums: List[int]) -> List[List[int]]:
res = []
for i in range(len(nums) + 1):
for tmp in itertools.combinations(nums, i):
res.append(tmp)
return res
""" 迭代 """
def subsets_2(self, nums: List[int]) -> List[List[int]]:
res = [[]]
for i in nums:
res = res + [[i] + num for num in res]
return res
""" """
def subsets_3(self, nums: List[int]) -> List[List[int]]:
res = []
n = len(nums)
def helper(i, tmp):
res.append(tmp)
for j in range(i, n):
helper(j + 1, tmp + [nums[j]])
helper(0, [])
return res
if __name__ == '__main__':
sol = Solution()
nums = [1, 2, 3, 4, 5]
res = sol.subsets_2(nums)
print(res)90. Subsets II
- 子集 II
"""
90. 子集 II
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
通过次数138,151提交次数218,019
"""
from typing import List
class Solution:
def subsetsWithDup_my00(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
def backtrack(idx, path, nums):
print(output)
print(path)
print(idx)
output.append(path)
for i in range(idx, n):
if i > idx and nums[i-1] == nums[i]: # 在第二个相同元素则过滤, i>idx为防止越界.
continue
backtrack(i+1, path+[nums[i]], nums)
output = []
nums.sort()
backtrack(0, [], nums)
return output
"""
对于 78. 子集 而言，找出没有重复数字的数组所有子集，按照模板，我们的思路应该是这样的：
未探索区域：剩余的未搜索的数组 nums[index: N - 1] ；
每个 path 是否满足题目的条件： 任何一个 path 都是子集，都满足条件，都要放到 res 中 ;
当前 path 满足条件时，是否继续搜索：是的，找到 nums[0:index-1] 中的子集之后， nums[index] 添加到老的 path 中会形成新的子集。
未探索区域当前可能的选择：每次选择可以选取 s 的 1 个字符，即 nums[index] ；
当前选择符合要求：任何 nums[index] 都是符合要求的，直接放到 path 中；
新的未探索区域：nums 在 index 之后的剩余字符串， nums[index + 1 : N - 1] 。
上面分析了那么多，让我们看看代码怎么写。由于每个path都是一个子集，都满足条件，所
作者：fuxuemingzhu
链接：https://leetcode-cn.com/problems/subsets-ii/solution/hui-su-fa-mo-ban-tao-lu-jian-hua-xie-fa-y4evs/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def subsetsWithDup_1(self, nums: List[int]) -> List[List[int]]:
res = []
n = len(nums)
nums.sort()
def helper(idx, tmp):
res.append(tmp)
for i in range(idx, n):
if i > idx and nums[i] == nums[i - 1]:
continue
helper(i + 1, tmp + [nums[i]])
helper(0, [])
return res
"""
思路:
思路二:迭代
作者：powcai
链接：https://leetcode-cn.com/problems/subsets-ii/solution/hui-su-suan-fa-by-powcai-6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def subsetsWithDup_2(self, nums: List[int]) -> List[List[int]]:
if not nums: return []
nums.sort()
res = [[]]
cur = []
for i in range(len(nums)):
if i > 0 and nums[i - 1] == nums[i]:
cur = [tmp + [nums[i]] for tmp in cur]
else:
cur = [tmp + [nums[i]] for tmp in res]
res += cur
return res
if __name__ == '__main__':
sol = Solution()
nums = [1, 2, 2, 3]
res = sol.subsetsWithDup_1(nums)四、分割问题
93. Restore IP Addresses
- 复原 IP 地址
"""
93. 复原 IP 地址
给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，
但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000"
输出：["0.0.0.0"]
示例 3：
输入：s = "1111"
输出：["1.1.1.1"]
示例 4：
输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]
示例 5：
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
0 <= s.length <= 3000
s 仅由数字组成
通过次数155,875提交次数288,188
请问您在哪类招聘中遇到此题？
"""
from typing import List
class Solution:
""" 正确, 思路, 分割每个节点+判断是否合法 """
def restoreIpAddresses_my00_write(self, s: str) -> List[str]:
def valid(x):
if x[0]=="0" and len(x)>1:
return False
if int(x)>255:
return False
return True
def backtrack(s, path):
if len(path) == 3 and s:
if valid(s):
output.append(".".join(path[:] + [s]))
return
print(path)
for i in range(min(len(s), 3)):
if valid(s[:i+1]):
backtrack(s[i+1:], path+[s[:i+1]])
output = []
backtrack(s, [])
return output
"""
方法一：回溯
思路与算法
由于我们需要找出所有可能复原出的 IP 地址，因此可以考虑使用回溯的方法，对所有可能的字符串分隔方式进行搜索，并筛选出满足要求的作为答案。
设题目中给出的字符串为 ss。我们用递归函数 dfs(segId,segStart) 表示我们正在从 s[segStart] 的位置开始，
搜索 IP 地址中的第 segId 段，其中 segId∈{0,1,2,3}。由于 IP 地址的每一段必须是 [0,255] 中的整数，
因此我们从 segStart 开始，从小到大依次枚举当前这一段 IP 地址的结束位置 segEnd。
，就递归地进行下一段搜索，调用递归函数 dfs(segId+1,segEnd+1)。
特别地，由于 IP 地址的每一段不能有前导零，因此如果 s[segStart] 等于字符 00，
那么 IP 地址的第 segId 段只能为 0，需要作为特殊情况进行考虑。
在搜索的过程中，如果我们已经得到了全部的 4 段 IP 地址（即 segId=4），
并且遍历完了整个字符串（即 segStart=∣s∣，其中 |s|∣s∣ 表示字符串 ss 的长度），
那么就复原出了一种满足题目要求的 IP 地址，我们将其加入答案。在其它的时刻，
如果提前遍历完了整个字符串，那么我们需要结束搜索，回溯到上一步。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/restore-ip-addresses/solution/fu-yuan-ipdi-zhi-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def restoreIpAddresses_offical_1(self, s: str) -> List[str]:
SEG_COUNT = 4
ans = list()
segments = [0] * SEG_COUNT
def dfs(segId: int, segStart: int):
# 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
if segId == SEG_COUNT:
if segStart == len(s):
ipAddr = ".".join(str(seg) for seg in segments)
ans.append(ipAddr)
return
# 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
if segStart == len(s):
return
# 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
if s[segStart] == "0":
segments[segId] = 0
dfs(segId + 1, segStart + 1)
# 一般情况，枚举每一种可能性并递归
addr = 0
for segEnd in range(segStart, len(s)):
addr = addr * 10 + (ord(s[segEnd]) - ord("0"))
if 0 < addr <= 0xFF:
segments[segId] = addr
dfs(segId + 1, segEnd + 1)
else:
break
dfs(0, 0)
return ans
"""
使用列表， 求出每段后再通过 join() 函数拼接
28 ms , 在所有 Python3 提交中击败了 96.41% 的用户
"""
def restoreIpAddresses_2(self, s: str) -> list:
"""
一共四位，每一位都可以取 0 - 255之间这些数字，也就是，每一位都可以取 1 - 3位，也就是每一位都有三种取法。
抽象出来就是四层，三叉树。
从中去掉不符合规则的就可以了。
"""
if len(s) < 4: return []
rst = []
def getIP(IP: list, idx):
# 4. 长度大于 4 剪枝
if len(IP) == 4:
# 5. 正好取完，才对
if idx == len(s):
rst.append('.'.join(IP))
return
for i in range(1, 4):
# 3. 这个可加可不加，是因为 假如 'ab' 切片长度大于 2，都是 取ab，那么会取到两个相同结果，但是5会限制，只有idx == len(s) 才会取
if idx + i > len(s):
continue
sub = s[idx: idx + i]
# 1. 包含前导0， 剪枝
if len(sub) > 1 and sub[0] == '0':
continue
# 2. 当取得这一位大于255，直接剪枝
if int(sub) > 255:
continue
IP.append(sub)
getIP(IP, idx + i)
IP.pop()
getIP([], 0)
return rst
if __name__ == '__main__':
s = "010010"
sol = Solution()
res = sol.restoreIpAddresses_offical_1(s)
print(res)
""" 回溯, 分割每个节点+判断是否合法 """131. Palindrome Partitioning
- 分割回文串
"""131. 分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
提示：
1 <= s.length <= 16
s 仅由小写英文字母组成
通过次数135,460提交次数187,348
请问您在哪类招聘中遇到此题？
"""
from typing import List
class Solution:
def partition_my00_make(self, s: str) -> List[List[str]]:
def vaild(x): # 校验是否是回文
if x == x[::-1]:
return True
return False
def backtrack(idx, path):
# print(path[:])
if len_s - idx == 0: # 终止条件
output.append(path[:])
return
for i in range(len_s-idx): # 回文迭代
if vaild(s[idx:idx+i+1]):
backtrack(idx+i+1, path+[s[idx:idx+i+1]])
# else:
# break
len_s = len(s)
output = []
backtrack(0, [])
return output
"""
方法一：回溯 + 动态规划预处理
思路与算法
由于需要求出字符串 ss 的所有分割方案，因此我们考虑使用搜索 + 回溯的方法枚举所有可能的分割方法并进行判断。
假设我们当前搜索到字符串的第 ii 个字符，且 s[0..i−1] 位置的所有字符已经被分割成若干个回文串，
并且分割结果被放入了答案数组 ans 中，那么我们就需要枚举下一个回文串的右边界 j，使得 s[i..j] 是一个回文串。
因此，我们可以从 i 开始，从小到大依次枚举 j。对于当前枚举的 j 值，我们使用双指针的方法判断 s[i..j] 是否为回文串：
如果 s[i..j] 是回文串，那么就将其加入答案数组 ans 中，并以 j+1 作为新的 i 进行下一层搜索，并在未来的回溯时将 s[i..j] 从 ans 中移除。
如果我们已经搜索完了字符串的最后一个字符，那么就找到了一种满足要求的分割方法。
细节
当我们在判断 s[i..j] 是否为回文串时，常规的方法是使用双指针分别指向 i 和 j，每次判断两个指针指向的字符是否相同，直到两个指针相遇。
然而这种方法会产生重复计算，例如下面这个例子：
当 s=aaba 时，对于前 2 个字符 aa，我们有 2 种分割方法 [aa] 和 [a,a]，
当我们每一次搜索到字符串的第 i=2 个字符 b 时，都需要对于每个 s[i..j] 使用双指针判断其是否为回文串，这就产生了重复计算。
因此，我们可以将字符串 s 的每个子串 s[i..j] 是否为回文串预处理出来，使用动态规划即可。
设 f(i,j) 表示 s[i..j] 是否为回文串，那么有状态转移方程：
f(i,j) = { True, i≥j
f(i+1,j−1)∧(s[i]=s[j]), otherwise
其中 ∧ 表示逻辑与运算，即s[i..j] 为回文串，当且仅当其为空串（i>j），其长度为 1（i=j），或者首尾字符相同且 s[i+1..j−1] 为回文串。
预处理完成之后，我们只需要 O(1) 的时间就可以判断任意 s[i..j] 是否为回文串了。
复杂度分析
时间复杂度：O(n⋅2^n)，其中 n 是字符串 s的长度。在最坏情况下，s 包含 n 个完全相同的字符，因此它的任意一种划分方法都满足要求。
而长度为 n 的字符串的划分方案数为 2^{n-1}=O(2^n)，
每一种划分方法需要 O(n) 的时间求出对应的划分结果并放入答案，因此总时间复杂度为 O(n⋅2^n)。
尽管动态规划预处理需要 O(n^2) 的时间，但在渐进意义下小于 O(n⋅2^n)，因此可以忽略。
空间复杂度：
O(n^2)，这里不计算返回答案占用的空间。数组 f 需要使用的空间为 O(n^2)，
而在回溯的过程中，我们需要使用 O(n) 的栈空间以及 O(n) 的用来存储当前字符串分割方法的空间。
由于 O(n) 在渐进意义下小于 O(n^2)，因此空间复杂度为 O(n^2)。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/palindrome-partitioning/solution/fen-ge-hui-wen-chuan-by-leetcode-solutio-6jkv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def partition_offical_1(self, s: str) -> List[List[str]]:
# 状态
n = len(s)
f = [[True] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
f[i][j] = (s[i] == s[j]) and f[i + 1][j - 1]
ret = list()
ans = list()
def dfs(i: int):
if i == n:
ret.append(ans[:])
return
for j in range(i, n):
if f[i][j]:
ans.append(s[i:j + 1])
dfs(j + 1)
ans.pop()
dfs(0)
return ret
"""
方法二：回溯 + 记忆化搜索
思路与算法
方法一中的动态规划预处理计算出了任意的 s[i..j] 是否为回文串，我们也可以将这一步改为记忆化搜索。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/palindrome-partitioning/solution/fen-ge-hui-wen-chuan-by-leetcode-solutio-6jkv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def partition_offical_2(self, s: str) -> List[List[str]]:
n = len(s)
ret = list()
ans = list()
@cache
def isPalindrome(i: int, j: int) -> int:
if i >= j:
return 1
return isPalindrome(i + 1, j - 1) if s[i] == s[j] else -1
def dfs(i: int):
if i == n:
ret.append(ans[:])
return
for j in range(i, n):
if isPalindrome(i, j) == 1:
ans.append(s[i:j + 1])
dfs(j + 1)
ans.pop()
dfs(0)
isPalindrome.cache_clear()
return ret
if __name__ == '__main__':
s = "aab"
s = "efe"
sol = Solution()
res = sol.partition_offical_1(s)
print(res)
"""
回溯 + 记忆化搜索
"""五、棋盘问题
51. N-Queens
- N 皇后
"""
51. N 皇后
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
注意: N皇后问题 题目: 八皇后问题:在8 X 8的国际象棋上摆放八个皇后,使其不能相互攻击,即任意两个皇后不得处于同一行,同一列或者同意对角线上
示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：[["Q"]]
提示：
1 <= n <= 9
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
通过次数153,775提交次数208,227
"""
from typing import List
import numpy as np
import copy
class Solution:
"""
方法一：基于集合的回溯
为了判断一个位置所在的列和两条斜线上是否已经有皇后，使用三个集合columns、diagonals-1和diagonals-2
分别记录每一列以及两个方向的每条斜线上是否有皇后。
列的表示法很直观，一共有 N 列，每一列的下标范围从 0 到 N-1，使用列的下标即可明确表示每一列。
如何表示两个方向的斜线呢？对于每个方向的斜线，需要找到斜线上的每个位置的行下标与列下标之间的关系。
方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 (0,0) 和 (3,3) 在同一条方向一的斜线上。
因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。
复杂度分析:
时间复杂度：O(N!)，其中 N 是皇后数量。
空间复杂度：O(N)，其中 N 是皇后数量。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合，
递归调用层数不会超过 N，数组的长度为 N，每个集合的元素个数都不会超过 N。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/n-queens/solution/nhuang-hou-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def solveNQueens_offical_1(self, n: int) -> List[List[str]]:
def generateBoard():
board = list()
for i in range(n):
row[queens[i]] = "Q"
board.append("".join(row))
row[queens[i]] = "."
return board
def backtrack(row: int):
if row == n:
board = generateBoard()
solutions.append(board)
else:
for i in range(n):
if i in columns or row - i in diagonal1 or row + i in diagonal2:
continue
queens[row] = i
columns.add(i)
diagonal1.add(row - i)
diagonal2.add(row + i)
backtrack(row + 1)
columns.remove(i)
diagonal1.remove(row - i)
diagonal2.remove(row + i)
solutions = list()
queens = [-1] * n
columns = set()
diagonal1 = set()
diagonal2 = set()
row = ["."] * n
backtrack(0)
return solutions
"""
方法二：基于位运算的回溯
方法一使用三个集合记录分别记录每一列以及两个方向的每条斜线上是否有皇后，每个集合最多包含 N 个元素，因此集合的空间复杂度是 O(N)。
如果利用位运算记录皇后的信息，就可以将记录皇后信息的空间复杂度从 O(N) 降到 O(1)。
具体做法是，使用三个整数 columns、diagonals 1 和 diagonals 2分别记录每一列以及两个方向的每条斜线上是否有皇后，每个整数有 N 个二进制位。
棋盘的每一列对应每个整数的二进制表示中的一个数位，其中棋盘的最左列对应每个整数的最低二进制位，最右列对应每个整数的最高二进制位。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/n-queens/solution/nhuang-hou-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def solveNQueens_offical_2(self, n: int) -> List[List[str]]:
def generateBoard():
board = list()
for i in range(n):
row[queens[i]] = "Q"
board.append("".join(row))
row[queens[i]] = "."
return board
def solve(row: int, columns: int, diagonals1: int, diagonals2: int):
if row == n:
board = generateBoard()
solutions.append(board)
else:
availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2))
while availablePositions:
position = availablePositions & (-availablePositions)
availablePositions = availablePositions & (availablePositions - 1)
column = bin(position - 1).count("1")
queens[row] = column
solve(row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1)
solutions = list()
queens = [-1] * n
row = ["."] * n
solve(0, 0, 0, 0)
return solutions
"""
单层搜索的逻辑
递归深度
就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。
每次都是要从新的一行的起始位置开始搜，所以都是从0开始。
验证***是否合法
按照如下标准去重：
不能同行
不能同列
不能同斜线 （45度和135度角）
作者：carlsun-2
链接：https://leetcode-cn.com/problems/n-queens/solution/dai-ma-sui-xiang-lu-51-n-queenshui-su-fa-2k32/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def solveNQueens_2(self, n: int) -> List[List[str]]:
if not n: return []
board = [['.'] * n for _ in range(n)]
res = []
def isVaild(board, row, col):
# 判断同一列是否冲突
for i in range(len(board)):
if board[i][col] == 'Q':
return False
# 判断左上角是否冲突
i = row - 1
j = col - 1
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
# 判断右上角是否冲突
i = row - 1
j = col + 1
while i >= 0 and j < len(board):
if board[i][j] == 'Q':
return False
i -= 1
j += 1
return True
def backtracking(board, row, n):
# 如果走到最后一行，说明已经找到一个解
if row == n:
temp_res = []
for temp in board:
temp_str = "".join(temp)
temp_res.append(temp_str)
res.append(temp_res)
for col in range(n):
if not isVaild(board, row, col):
continue
board[row][col] = 'Q'
backtracking(board, row + 1, n)
board[row][col] = '.'
backtracking(board, 0, n)
return res
"""
回溯算法
记录 行, 列, 正对角,负对角,不能有两个以上的棋子.
如何判断是否在对角上呢?
正对角就是相加之和一样的
负对角就是相减只差一样的
"""
def solveNQueens_3(self, n: int) -> List[List[str]]:
res = []
s = "." * n
def backtrack(i, tmp, col, z_diagonal, f_diagonal):
if i == n:
res.append(tmp)
return
for j in range(n):
if j not in col and i + j not in z_diagonal and i - j not in f_diagonal:
backtrack(i + 1,
tmp + [s[:j] + "Q" + s[j + 1:]],
col | {j},
z_diagonal | {i + j},
f_diagonal | {i - j})
backtrack(0, [], set(), set(), set())
return res
if __name__ == '__main__':
n = 4
sol = Solution()
res = sol.solveNQueens_offical_1(n)
print(res)52. N-Queens II
- N皇后 II
"""
52. N皇后 II
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
示例 1：
输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：1
提示：
1 <= n <= 9
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
通过次数74,703提交次数90,796
请问您在哪类招聘中遇到此题？
"""
class Solution:
"""
回顾这道题，拿到这道题的时候，其实我们很容易看出需要使用枚举的方法来求解这个问题，
当我们不知道用什么办法来枚举是最优的时候，可以从下面三个方向考虑：
子集枚举：可以把问题转化成「从 n^2 个格子中选一个子集，使得子集中恰好有 nn 个格子，且任意选出两个都不在同行、同列或者同对角线」，这里枚举的规模是 2^{n^2}；
组合枚举：可以把问题转化成「从 n^2 个格子中选择 n 个，且任意选出两个都不在同行、同列或者同对角线」，这里的枚举规模是 {n^2}；
排列枚举：因为这里每行只能放置一个皇后，而所有行中皇后的列号正好构成一个 11 到 nn 的排列，所以我们可以把问题转化为一个排列枚举，规模是 n!。
带入一些 nn 进这三种方法验证，就可以知道哪种方法的枚举规模是最小的，这里我们发现第三种方法的枚举规模最小。这道题给出的两个方法其实和排列枚举的本质是类似的。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/n-queens-ii/solution/nhuang-hou-ii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def totalNQueens_my00(self, n: int) -> int:
# idx - i, idx+i 用于存储判断对角线上的格子是否被占用
import copy
def backtrack(idx, column, diagonal_1, diagonal_2):
if idx == n:
# output.append(copy.deepcopy(matrix[:]))
output += 1
return
for i in range(n):
if i in column or idx-i in diagonal_1 or idx+i in diagonal_2:
continue
diagonal_2.add(idx+i)
diagonal_1.add(idx-i)
column.add(i)
# matrix[idx][i] = "Q"
# print(matrix[:])
backtrack(idx+1, column, diagonal_1, diagonal_2)
# matrix[idx][i] = "."
diagonal_2.remove(idx+i)
diagonal_1.remove(idx-i)
column.remove(i)
# matrix = [["."] * n for _ in range(n)]
# output = []
output = 0
backtrack(0, set(), set(), set())
# print(output)
# return len(output)
return output
"""
方法一：回溯法+set集合
思路
正对角线（从左上到右下）的特点：横纵坐标之差相同
副对角线（从右上到左下）的特点：横纵坐标之和相同
每行、每列及正副对角线上只能出现一个皇后，由于从上到下放置皇后，所以只需考虑当前坐标对应的列和正副对角线是否已被访问即可
定义变量
i：横坐标
j：纵坐标
col：set集合，存储遍历过的列j
pos：set集合，存储正对角线之差i-j
neg：set集合，存储副对角线之和i+j
步骤
做选择：如果该坐标上对应的列和正副对角线上没有皇后，放置皇后并在对应集合中标记
递归：进入下一行
撤销选择：将当前标记从三个集合中删除
复杂度分析
时间复杂度：O(N!)
空间复杂度：O(N)
代码
作者：yim-6
链接：https://leetcode-cn.com/problems/n-queens-ii/solution/python3-san-chong-fang-fa-shi-xian-nhuang-hou-ii-b/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def totalNQueens_1(self, n: int) -> int:
col = set()
pos = set()
neg = set()
res = 0
def backtrack(i):
nonlocal res
if i == n:
res += 1
return
for j in range(n):
if j not in col and i - j not in pos and i + j not in neg:
# 做选择
col.add(j)
pos.add(i - j)
neg.add(i + j)
# 递归进入下一行
backtrack(i + 1)
# 撤销选择
col.remove(j)
pos.remove(i - j)
neg.remove(i + j)
backtrack(0)
return res
"""
方法二：回溯法+位运算
思路
N个位置可以对应成N个二进制位
二进制位状态
0：无皇后，可选择
1：有皇后，不可选
比如八皇后第一行状态为0000 0000，当第二位被选择后该行的状态变成了0100 0000，下一行同样第二位不能被选，正对角线对应的第三位不能被选（对应当前行右移了一位），副对角线对应的第一位不能被选（对应当前行左移了一位）
已选列的二进制表示：0100 0000
已选正对角线的二进制表示：0010 0000
已选副对角线的二进制表示：1000 0000
定义变量
i：横坐标
j：纵坐标
col：已选列的二进制位
pos：已选正对角线的二进制位
neg：已被副对角线的二进制位
步骤
将col、pos和neg做或运算（|）得到的二进制位pre中，1表示不能被选的位置，0表示可以被选的位置
遍历N位二进制，如果当前可被选择，则将该位置加入到对应二进制中，同时正对角线pos右移一位，副对角线neg左移一位
递归执行上述操作，直到所有选择执行完成
复杂度分析
时间复杂度：O(N!)
空间复杂度：O(N)
作者：yim-6
链接：https://leetcode-cn.com/problems/n-queens-ii/solution/python3-san-chong-fang-fa-shi-xian-nhuang-hou-ii-b/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def totalNQueens_2(self, n: int) -> int:
res = 0
def backtrack(index, col, pos, neg):
nonlocal res
if index == n:
res += 1
return
# 获取可供选择的状态位，1为不可选，0为可选
pre = col | pos | neg
for i in range(n):
cur = 1 << i
if cur & pre == 0:
backtrack(index + 1, col | cur, (pos | cur) >> 1, (neg | cur) << 1)
backtrack(0, 0, 0, 0)
return res
"""
位运算优化
上面是对二进制的每一位进行判断是否可选，优化之处是只对1位置进行操作，具体方法：
将col、pos和neg执行或运算后，得到的二进制取反后1为可选，0为不可选
因为棋盘大小为N，所以需保证二进制取反后也为N位，方法是与N位1的二进制执行与运算
获取最低位1的二进制位cur=pre & (-pre)，将该位放置皇后，并修改col、pos和neg状态，进入下一层递归
如果本次选择不能达到最终目的，将撤销本次操作，并寻找下一个1出现的位置pre&=pre-1
作者：yim-6
链接：https://leetcode-cn.com/problems/n-queens-ii/solution/python3-san-chong-fang-fa-shi-xian-nhuang-hou-ii-b/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def totalNQueens_3(self, n: int) -> int:
res = 0
def backtrack(i, col, pos, neg):
nonlocal res
if i == n:
res += 1
return
# 其中1表示可以被选
pre = ((1 << n) - 1) & (~(col | pos | neg))
while pre:
cur = pre & (-pre)
backtrack(i + 1, col | cur, (pos | cur) >> 1, (neg | cur) << 1)
pre &= pre - 1
backtrack(0, 0, 0, 0)
return res
if __name__ == '__main__':
n = 4
sol = Solution()
res = sol.totalNQueens_1(n)
print(res)
# 回溯, 重点要考虑对角线等五、字符串回溯问题
22. Generate Parentheses
- 括号生成
"""
22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足：左括号必须以正确的顺序闭合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8
通过次数349,373提交次数452,243
"""
class Solution:
"""
方法三：按括号序列的长度递归
思路与算法
任何一个括号序列都一定是由 ( 开头，并且第一个 ( 一定有一个唯一与之对应的 )。这样一来，每一个括号序列可以用 (a)b 来表示，其中 a 与 b 分别是一个合法的括号序列（可以为空）。
那么，要生成所有长度为 2 * n 的括号序列，我们定义一个函数 generate(n) 来返回所有可能的括号序列。那么在函数 generate(n) 的过程中：
我们需要枚举与第一个 ( 对应的 ) 的位置 2 * i + 1；
递归调用 generate(i) 即可计算 a 的所有可能性；
递归调用 generate(n - i - 1) 即可计算 b 的所有可能性；
遍历 a 与 b 的所有可能性并拼接，即可得到所有长度为 2 * n 的括号序列。
为了节省计算时间，我们在每次 generate(i) 函数返回之前，把返回值存储起来，下次再调用 generate(i) 时可以直接返回，不需要再递归计算。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/generate-parentheses/solution/gua-hao-sheng-cheng-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def generateParenthesis_offical_3(self, N):
if N == 0: return [""]
ans = []
print(ans)
for c in range(N):
for left in self.generateParenthesis_offical_3(c):
for right in self.generateParenthesis_offical_3(N - 1 - c):
ans.append("({}){}".format(left, right))
return ans
"""
方法一：暴力法
思路
我们可以生成所有 2^{2n}个 '(' 和 ')' 字符构成的序列，然后我们检查每一个是否有效即可。
算法
为了生成所有序列，我们可以使用递归。长度为 n 的序列就是在长度为 n-1 的序列前加一个 '(' 或 ')'。
为了检查序列是否有效，我们遍历这个序列，并使用一个变量 balance 表示左括号的数量减去右括号的数量。
如果在遍历过程中 balance 的值小于零，或者结束时 balance 的值不为零，那么该序列就是无效的，否则它是有效的。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/generate-parentheses/solution/gua-hao-sheng-cheng-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def generateParenthesis_offical_1(self, n: int):
def generate(A):
if len(A) == 2 * n:
if valid(A):
ans.append("".join(A))
else:
A.append('(')
generate(A)
A.pop()
A.append(')')
generate(A)
A.pop()
def valid(A):
bal = 0
for c in A:
if c == '(':
bal += 1
else:
bal -= 1
if bal < 0: return False
return bal == 0
ans = []
generate([])
return ans
"""
方法二：回溯法
思路和算法
方法一还有改进的余地：我们可以只在序列仍然保持有效时才添加 '(' or ')'，而不是像 方法一 那样每次添加。
我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，
如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/generate-parentheses/solution/gua-hao-sheng-cheng-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def generateParenthesis_offical_2(self, n: int):
ans = []
def backtrack(S, left, right):
if len(S) == 2 * n:
ans.append(''.join(S))
return
if left < n:
S.append('(')
backtrack(S, left + 1, right)
S.pop()
if right < left:
S.append(')')
backtrack(S, left, right + 1)
S.pop()
backtrack([], 0, 0)
return ans
if __name__ == "__main__":
sol = Solution()
res = sol.generateParenthesis_offical_2(4)
for r in res:
print(r)17. Letter Combinations of a Phone Number
- 电话号码的字母组合
"""
17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4
digits[i] 是范围 ["2", "9"] 的一个数字。
通过次数338,093提交次数590,576
"""
from typing import List
class Solution:
""" 重点要想到字典, 哈希表
这题 回溯 = 递归 + 保存值
类似于for循环遍历了
"""
def letterCombinations_my00(self, digits: str) -> List[str]:
if not digits:
return []
phone = {"2": ["a", "b", "c"],
"3": ["d", "e", "f"],
"4": ["g", "h", "i"],
"5": ["j", "k", "l"],
"6": ["m", "n", "o"],
"7": ["p", "q", "r", "s"],
"8": ["t", "u", "v"],
"9": ["w", "x", "y", "z"]}
self.res = []
# way---1
# def backtrack(word, phone, path):
# if len(word) == 0:
# self.res += path
# return
# chars = phone.get(word[0])
# path = [p + ch for p in path for ch in chars]
# backtrack(word[1:], phone, path)
# backtrack(digits, phone, [""])
# way---2
def backtrack(word, path):
if len(word) == 0:
self.res.append(path)
return
chars = phone.get(word[0])
for c in chars:
backtrack(word[1:], path+c)
backtrack(digits, "")
return self.res
"""
方法一：回溯
当题目中出现 “所有组合” 等类似字眼时，我们第一感觉就要想到用回溯。
定义函数 backtrack(combination, nextdigit)，当 nextdigit 非空时，对于 nextdigit[0] 中的每一个字母 letter，
执行回溯 backtrack(combination + letter,nextdigit[1:]，直至 nextdigit 为空。最后将 combination 加入到结果中。
作者：z1m
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/hui-su-dui-lie-tu-jie-by-ml-zimingmeng/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def letterCombinations_1(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
phone = {'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']}
def backtrack(combination, next_digits):
# if there is no more digits to check
if len(next_digits) == 0:
# the combination is done
output.append(combination)
# if there are still digits to check
else:
# iterate over all letters which map
# the next available digit
for letter in phone[next_digits[0]]:
# append the current letter to the combination
# and proceed to the next digits
backtrack(combination + letter, next_digits[1:])
output = []
if digits:
backtrack("", digits)
return output
"""
法二：队列
我们也可以使用队列，先将输入的 digits 中第一个数字对应的每一个字母入队，然后将出队的元素与第二个数字对应的每一个字母组合后入队...直到遍历到 digits 的结尾。最后队列中的元素就是所求结果。
复杂度分析
时间复杂度：O(3^M×4^N)。MM 是对应三个字母的数字个数，NN 是对应四个字母的数字个数。
空间复杂度：O(3^M×4^N)。一共要生成 3^M×4^N个结果。
作者：z1m
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/hui-su-dui-lie-tu-jie-by-ml-zimingmeng/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def letterCombinations_2(self, digits: str) -> List[str]:
if not digits: return []
phone = ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
queue = [''] # 初始化队列
for digit in digits:
for _ in range(len(queue)):
tmp = queue.pop(0)
for letter in phone[ord(digit) - 50]: # 这里我们不使用 int() 转换字符串，使用ASCII码
queue.append(tmp + letter)
return queue
if __name__ == "__main__":
sol = Solution()
strs = "349" # ["dog","racecar","car"]
res = sol.letterCombinations_my00(strs)
print(res)
gg = 0
"""
题目中出现 “所有组合” , 回溯,
对于所有可能存在的进行符号进行遍历
"""六、泛洪填充(Flood Fill)
79. Word Search
- 单词搜索
"""
79. 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]], word = "SEE"
输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
提示：
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成
进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
通过次数165,226提交次数369,429
请问您在哪类招聘中遇到此题？
"""
from typing import List
class Solution:
"""
方法一：回溯
思路与算法
设函数 \text{check}(i, j, k)check(i,j,k) 表示判断以网格的 (i, j)(i,j) 位置出发，能否搜索到单词 \textit{word}[k..]word[k..]，其中 \textit{word}[k..]word[k..] 表示字符串 \textit{word}word 从第 kk 个字符开始的后缀子串。如果能搜索到，则返回 \texttt{true}true，反之返回 \texttt{false}false。函数 \text{check}(i, j, k)check(i,j,k) 的执行步骤如下：
如果 \textit{board}[i][j] \neq s[k]board[i][j]
=s[k]，当前字符不匹配，直接返回 \texttt{false}false。
如果当前已经访问到字符串的末尾，且对应字符依然匹配，此时直接返回 \texttt{true}true。
否则，遍历当前位置的所有相邻位置。如果从某个相邻位置出发，能够搜索到子串 \textit{word}[k+1..]word[k+1..]，则返回 \texttt{true}true，否则返回 \texttt{false}false。
这样，我们对每一个位置 (i,j)(i,j) 都调用函数 \text{check}(i, j, 0)check(i,j,0) 进行检查：只要有一处返回 \texttt{true}true，就说明网格中能够找到相应的单词，否则说明不能找到。
为了防止重复遍历相同的位置，需要额外维护一个与 \textit{board}board 等大的 \textit{visited}visited 数组，用于标识每个位置是否被访问过。每次遍历相邻位置时，需要跳过已经被访问的位置。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/word-search/solution/dan-ci-sou-suo-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def exist_offical_1(self, board: List[List[str]], word: str) -> bool:
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def check(i: int, j: int, k: int) -> bool:
if board[i][j] != word[k]:
return False
if k == len(word) - 1:
return True
visited.add((i, j))
result = False
for di, dj in directions:
newi, newj = i + di, j + dj
if 0 <= newi < len(board) and 0 <= newj < len(board[0]):
if (newi, newj) not in visited:
if check(newi, newj, k + 1):
result = True
break
visited.remove((i, j))
return result
h, w = len(board), len(board[0])
visited = set()
for i in range(h):
for j in range(w):
if check(i, j, 0):
return True
return False
""" DFS + 循环遍历。早先时候做这种题目还是很头痛的，现在已经很OK了，还是有进步的
"""
def exist_2(self, board: List[List[str]], word: str) -> bool:
m, n = len(board), len(board[0])
def helper(lenth, x, y):
if x < 0 or x > m - 1 or y < 0 or y > n - 1:
return False
if lenth == len(word) - 1 and board[x][y] == word[lenth]:
return True
if board[x][y] == word[lenth]:
board[x][y] = '.'
if helper(lenth + 1, x, y + 1) or helper(lenth + 1, x, y - 1) or \
helper(lenth + 1, x + 1,y) or helper(lenth + 1, x - 1, y):
return True
else:
board[x][y] = word[lenth]
return
for i in range(m):
for j in range(n):
if helper(0, i, j):
return True
return False
# 定义上下左右四个行走方向for试探, 回溯 + DFS
def exist_3(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
m = len(board)
if m == 0:
return False
n = len(board[0])
mark = [[0 for _ in range(n)] for _ in range(m)]
def backtrack(i, j, mark, board, word):
if len(word) == 0:
return True
for direct in directs:
cur_i = i + direct[0]
cur_j = j + direct[1]
if cur_i >= 0 and cur_i < len(board) and cur_j >= 0 and cur_j < len(board[0]) \
and board[cur_i][cur_j] == word[0]:
# 如果是已经使用过的元素，忽略
if mark[cur_i][cur_j] == 1:
continue
# 将该元素标记为已使用
mark[cur_i][cur_j] = 1
if backtrack(cur_i, cur_j, mark, board, word[1:]) == True:
return True
else:
# 回溯
mark[cur_i][cur_j] = 0
return False
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == word[0]:
# 将该元素标记为已使用
mark[i][j] = 1
if backtrack(i, j, mark, board, word[1:]) == True:
return True
else:
# 回溯
mark[i][j] = 0
return False
"""
Python做DFS、回溯，简直就是在超时的边缘疯狂试探...
这道题初看很简单，但是想想会发现细节很多。
word的起始位置在board中可能存在多个，需要循环后在开始搜索。
我们在查找的过程中，需要判断下一个符合规律的方格，我们是否之前走过了，比如[["A","B"],["C","D"]],
"ABCDA".这个用例如果没有记录是否访问过，就会导致异常。
对于已访问的路径标记，可以维护一个visited的dict(tuple)，但如果题目没有明确说不能修改原数组，那么修改原数组不失为更简洁省空间的方式。
关注到这两个细节，套用DFS+回溯的基本公式，就能顺利AC了...
作者：qingfengpython
链接：https://leetcode-cn.com/problems/word-search/solution/79dan-ci-sou-suo-li-jie-liang-ge-xiao-ke-rh6b/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def exist_simple(self, board, word):
""" 原来的矩阵board上修改作为board, 内存, 定义上下左右四个行走方向for试探, 回溯 + DFS """
directs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
row, col = len(board), len(board[0])
def dfs(x, y, index):
if board[x][y] != word[index]:
return False
if index == len(word) - 1:
return True
board[x][y] = '#'
for choice in directs:
nx, ny = x + choice[0], y + choice[1]
if 0 <= nx < row and 0 <= ny < col and dfs(nx, ny, index + 1):
return True
board[x][y] = word[index]
for i in range(row):
for j in range(col):
if dfs(i, j, 0):
return True
return False
if __name__ == '__main__':
sol = Solution()
nums = [1, 2, 3]
board = [["A", "B", "C", "E"],
["S", "F", "C", "S"],
["A", "D", "E", "E"]]
word = "SEE"
res = sol.exist_my20210918(board, word)
print(res)
""" 矩阵搜索, 定义上下左右四个行走方向for试探, 回溯 + DFS """130. Surrounded Regions
- 被围绕的区域
"""
130. 被围绕的区域
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例 1：
输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
示例 2：
输入：board = [["X"]]
输出：[["X"]]
提示：
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 'X' 或 'O'
通过次数126,980提交次数285,944
"""
from typing import List
class Solution:
### 开始的思路从O开始找里边的，烦琐了
def solve_my_error(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
m = len(board[0])
n = len(board)
visited = [[0 for mi in range(m)] for ni in range(n)]
directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def bactrack(i, j, ij_choices):
flag = 0
for direct in directs:
curr_i = i + direct[0]
curr_j = j + direct[1]
if not visited[curr_i][curr_j] and board[curr_i][curr_i] != "O":
flag = 1
if flag:
return True
ij_choices.append((i,j))
for direct in directs:
curr_i = i + direct[0]
curr_j = j + direct[1]
# if curr_i == 2 and curr_j == 2:
# ee = 0
if 0 < curr_i < m-1 and 0 < curr_i < n-1 and board[curr_i][curr_i] == "O":
if visited[curr_i][curr_j] == 1:
continue
visited[curr_i][curr_j] = 1
if bactrack(curr_i, curr_j, ij_choices) == True:
return True
visited[curr_i][curr_j] = 0
return False
ij_choices_global = []
for i in range(m):
for j in range(n):
if i==1 and j==1:
ee = 0
if board[i][j] == "O" and not visited[i][j] and 0 < i < m-1 and 0 < j < n-1:
ij_choices = []
visited[i][j] = 1
if not bactrack(i, j, ij_choices):
ij_choices_global += ij_choices
else:
visited[i][j] = 0
print(ij_choices_global)
"""
写在前面
本题给定的矩阵中有三种元素：
字母 X；
被字母 X 包围的字母 O；
没有被字母 X 包围的字母 O。
本题要求将所有被字母 X 包围的字母 O都变为字母 X ，但很难判断哪些 O 是被包围的，哪些 O 不是被包围的。
注意到题目解释中提到：任何边界上的 O 都不会被填充为 X。 我们可以想到，所有的不被包围的 O 都直接或间接与边界上的 O 相连。我们可以利用这个性质判断 O 是否在边界上，具体地说：
对于每一个边界上的 O，我们以它为起点，标记所有与它直接或间接相连的字母 O；
最后我们遍历这个矩阵，对于每一个字母：
如果该字母被标记过，则该字母为没有被字母 X 包围的字母 O，我们将其还原为字母 O；
如果该字母没有被标记过，则该字母为被字母 X 包围的字母 O，我们将其修改为字母 X。
方法一：深度优先搜索
思路及解法
我们可以使用深度优先搜索实现标记操作。在下面的代码中，我们把标记过的字母 O 修改为字母 A。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/surrounded-regions/solution/bei-wei-rao-de-qu-yu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def solve_offical_1(self, board: List[List[str]]) -> None:
"""
从边界O出发, DFS-深度优先搜索
"""
if not board:
return
n, m = len(board), len(board[0])
def dfs(x, y):
if not 0 <= x < n or not 0 <= y < m or board[x][y] != 'O':
return
board[x][y] = "A"
dfs(x + 1, y)
dfs(x - 1, y)
dfs(x, y + 1)
dfs(x, y - 1)
### 横
for i in range(n):
dfs(i, 0)
dfs(i, m - 1)
### 竖
for i in range(m - 1):
dfs(0, i)
dfs(n - 1, i)
for i in range(n):
for j in range(m):
if board[i][j] == "A":
board[i][j] = "O"
elif board[i][j] == "O":
board[i][j] = "X"
""" 广度优先搜索, BFS """
def solve_offical_2(self, board: List[List[str]]) -> None:
import collections
if not board:
return
n, m = len(board), len(board[0])
que = collections.deque()
for i in range(n):
if board[i][0] == "O":
que.append((i, 0))
board[i][0] = "A"
if board[i][m - 1] == "O":
que.append((i, m - 1))
board[i][m - 1] = "A"
for i in range(m - 1):
if board[0][i] == "O":
que.append((0, i))
board[0][i] = "A"
if board[n - 1][i] == "O":
que.append((n - 1, i))
board[n - 1][i] = "A"
while que:
x, y = que.popleft()
for mx, my in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
if 0 <= mx < n and 0 <= my < m and board[mx][my] == "O":
que.append((mx, my))
board[mx][my] = "A"
for i in range(n):
for j in range(m):
if board[i][j] == "A":
board[i][j] = "O"
elif board[i][j] == "O":
board[i][j] = "X"
if __name__ == '__main__':
board = [["X", "X", "X", "X"],
["X", "O", "O", "X"],
["X", "X", "O", "X"],
["X", "O", "X", "X"]]
sol = Solution()
res = sol.solve_offical_2(board)
ee = 0
"""
依次从最外层四个边界 获取O改为A, 然后从该O使用BFS、DFS方式遍历改为A，最后其余的O改为X
"""200. Number of Islands
- 岛屿数量
"""
200. 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
示例 2：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'
通过次数325,497提交次数586,343
"""
from typing import List
class Solution:
"""
方法一：深度优先搜索
我们可以将二维网格看成一个无向图，竖直或水平相邻的 11 之间有边相连。
为了求出岛屿的数量，我们可以扫描整个二维网格。
如果一个位置为 11，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 11 都会被重新标记为 00。
最终岛屿的数量就是我们进行深度优先搜索的次数。
作者：LeetCode
链接：https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""
def numIslands_offical_1(self, grid: List[List[str]]) -> int:
def dfs(grid, r, c):
grid[r][c] = 0
nr, nc = len(grid), len(grid[0])
for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
dfs(grid, x, y)
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
num_islands = 0
for r in range(nr):
for c in range(nc):
if grid[r][c] == "1":
num_islands += 1
dfs(grid, r, c)
return num_islands
def numIslands_offical_2(self, grid: List[List[str]]) -> int:
import collections
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
num_islands = 0
for r in range(nr):
for c in range(nc):
if grid[r][c] == "1":
num_islands += 1
grid[r][c] = "0"
neighbors = collections.deque([(r, c)])
while neighbors:
row, col = neighbors.popleft()
for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
neighbors.append((x, y))
grid[x][y] = "0"
return num_islands
""" DFS, 不需要回溯 """
def numIslands_my_copy(self, grid: List[List[str]]) -> int:
""" grid[col][row]=grid[列][行] """
m = len(grid)
n = len(grid[0])
directs = [(0,1), (0,-1), (1,0), (-1,0)]
def dfs(i, j, grid):
grid[i][j] = "0"
for direct in directs:
curr_i = i + direct[0]
curr_j = j + direct[1]
if 0 <= curr_i < m and 0 <= curr_j < n and grid[curr_i][curr_j] == "1":
dfs(curr_i, curr_j, grid)
count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
count += 1
dfs(i, j, grid)
return count
if __name__ == '__main__':
grid = [
["1", "1", "0", "0", "0"],
["0", "1", "0", "0", "0"],
["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"]
]
print(grid[0][1])
print(grid[1][0])
sol = Solution()
res = sol.numIslands_my_copy(grid)
print(res)
ee = 0
"""
依次从最外层四个边界 获取O改为A, 然后从该O使用BFS、DFS方式遍历改为A，最后其余的O改为X
"""希望对你有所帮助!