给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 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]
]
链接：https://leetcode-cn.com/problems/combination-sum
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
result = []
def recursion( candidates: List[int], target: int, tmp_list: List[int]) :
#终止条件
if sum(tmp_list) == target:
#注意这时候是要copy一个新的list 纠正 并不需要 可以直接result.append(tmp_list) 减少时间
result.append(tmp_list[:])
return
#广度遍历
for i in candidates:
if sum(tmp_list)+ i >target:
break
#继续向下 深度搜索
new = list(filter(lambda x :x >=i , candidates))
#使用这种方式 tem+[i] 不需要 先 append 再 pop 不断地尝试不同组合
recursion(new, target, tmp_list+[i])
return
recursion(candidates, target, [])
return result
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
链接：https://leetcode-cn.com/problems/combination-sum-ii
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
result = []
tmp_list = []
def recursion( candidates: List[int], target: int, tmp: List[int]):
if sum(tmp) == target:
result.append(tmp[:])
return
for i in range(len(candidates)):
#剪枝处理
num = candidates[i]
if sum(tmp) + num > target:
break
#用来去重的部分 就是跳过兄弟节点相同的部分
if i > 0 and candidates[i] == candidates[i-1]:
continue
new = candidates[i+1:]
recursion(new, target, tmp+[num])
return
recursion(candidates, target, tmp_list)
return result
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
链接：https://leetcode-cn.com/problems/permutations
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
length = len(nums)
if len(nums) == 1:
return [nums]
def Traversal(tmp_nums:List[int], cur_len: int, tmp: List[int]):
if cur_len == length:
res.append(tmp)
return
for num in tmp_nums:
new = tmp_nums[:]
new.remove(num)
Traversal(new, cur_len+1, tmp+[num])
return
Traversal(nums, 0, [])
return res
可以学习参考下这里面的模板 主要有used数组
class Solution:
def permute(self, nums):
if len(nums) == 0:
return []
used = [False] * len(nums)
res = []
self.__dfs(nums, 0, [], used, res)
return res
def __dfs(self, nums, index, pre, used, res):
# 先写递归终止条件
if index == len(nums):
res.append(pre.copy())
return
for i in range(len(nums)):
if not used[i]:
# 如果没有用过，就用它
used[i] = True
pre.append(nums[i])
# 在 dfs 前后，代码是对称的
self.__dfs(nums, index + 1, pre, used, res)
used[i] = False
pre.pop()
作者：liweiwei1419
链接：https://leetcode-cn.com/problems/two-sum/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
链接：https://leetcode-cn.com/problems/permutations-ii
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
length = len(nums)
lastUsed = nums[0]
if len(nums) <= 1:
return [nums]
def Traversal(tmp_nums:List[int], cur_len: int, tmp: List[int]):
if cur_len == length:
res.append(tmp[:])
return
for i in range(len(tmp_nums)):
if i != 0 and tmp_nums[i] == tmp_nums[i-1]:
continue
Traversal(tmp_nums[:i]+tmp_nums[i+1:], cur_len+1, tmp+[tmp_nums[i]])
return
Traversal(nums, 0, [])
return res
#思想是先对nums数组进行排列，然后在递归的过程中维护一个lastUsed变量，存储本次迭代的for循环中最近使用的数字，如果下一轮循环的数字是lastUsed，就说明重复了，就跳过本次循环
#注意要比较的是 本次循环中 前后的数 不能相等 不是上下两级树的值不相等（是兄弟节点不同 不是父子节点）
#注意 lastUsed要在for循环遍历外面 进行初始化
#实际并不需要lastUsed 直接使用数组的元素即可 tmp_nums[i-1] == tmp_nums[i]
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
链接：https://leetcode-cn.com/problems/subsets
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
if len(nums) == 0:
return [[]]
nums.sort()
res = []
length = len(nums)
#两种方法 一种是保存每一次的 有新的数则 在原来的基础上 每个list都加这个数
"""
def recursion(num: int, cur_len :int):
if cur_len == 1:
res.append([])
res.append([num])
else:
sub = res[:]
for item in sub:
res.append(item+[num])
for index, num in enumerate(nums):
recursion(num, index+1)
return res
"""
""" 调用自身 直接遍历结果 增加新的元素
if length == 1:
return [[],[nums[0]]]
else:
sub = self.subsets(nums[:length-1])
for i in sub:
res.append(i+[nums[length-1]])
res.append(i)
#尝试使用回溯算法
def recursion(tmp: List[int], index: int):
res.append(tmp[:])
if index == length:
return
for i in range(index, length):
recursion(tmp+[nums[i]], i+1)
recursion([],0)
"""
#尝试自己的回溯方法
def recursion(tmp: List[int], index: int, tmp_nums: List[int]):
res.append(tmp[:])
if index == length:
return
for i in range(len(tmp_nums)):
recursion(tmp+[tmp_nums[i]], i+1, tmp_nums[i+1:])
recursion([], 0, nums)
return res
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
链接：https://leetcode-cn.com/problems/subsets-ii
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
if len(nums) == 0:
return [[]]
nums.sort()
res = []
length = len(nums)
"""
self.lastadd = 0
def recursion(num: int, cur_len :int):
if cur_len == 1:
res.append([])
res.append([num])
self.lastadd = 1
else:
sub = res[:]
for item in sub:
res.append(item+[num])
self.lastadd = len(res) - len(sub)
def recursion2(num: int, cur_len :int):
sub = res[len(res)-self.lastadd:]
for item in sub:
res.append(item+[num])
lastadd = len(sub)
for index, num in enumerate(nums):
if index > 0 and num == nums[index-1]:
recursion2(num, index+1)
#不同的数进行的是 原来的操作
else :
recursion(num, index+1)
#尝试使用回溯算法
def recursion(tmp: List[int], index: int, tmp_nums: List[int]):
res.append(tmp[:])
if index == length:
return
for i in range(len(tmp_nums)):
if i > 0 and tmp_nums[i] == tmp_nums[i-1]:
continue
recursion(tmp+[tmp_nums[i]], i+1, tmp_nums[i+1:])
recursion([], 0, nums)
"""
#使用回溯另外的表示方法 不需要另外保存 tmp_nums 直接用下标来表示
def recursion(tmp: List[int], index: int):
res.append(tmp[:])
if index == length:
return
for i in range(index, length):
#注意是 i> index 不是i》0
if i > index and nums[i] == nums[i-1]:
continue
recursion(tmp+[nums[i]], i+1)
recursion([], 0)
return res
简单的回溯应用
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
# 注意边界条件的判断考虑
if not digits:
return []
dic = {
"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"]
}
n = len(digits)
res = []
def recursion(tmp_res: str, deep: int):
if deep == n:
res.append(tmp_res)
return
#应该遍历的是 digits[deep] 对应的 数字的list
for tmp in dic[digits[deep]]:
recursion(tmp_res+ tmp, deep+1)
recursion("", 0)
return res
#如何分析回溯法的时间复杂度
自己先写的回溯法
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
# 初步感觉 可以用回溯 可以用出栈的办法
if not n :
return []
res = []
tmp = ""
brackets = ['(', ')']
left_num = 0
right_num = 0
def recursion(tmp_res: str, left_num: int, right_num: int, cur_len: int):
#print(tmp_res, left_num, right_num, cur_len)
if cur_len == 2*n:
res.append(tmp_res)
return
else:
for i in range(len(brackets)):
if brackets[i] == '(':
left_num += 1
else:
right_num += 1
if left_num < right_num or left_num > n or right_num > n:
#剪枝 是跳出循环吗
if brackets[i] == '(':
left_num -= 1
else:
right_num -= 1
continue
recursion(tmp_res+ brackets[i], left_num, right_num, cur_len+1)
if brackets[i] == '(':
left_num -= 1
else:
right_num -= 1
recursion("", 0, 0, 0)
return res
看着更简洁的方式
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
# 初步感觉 可以用回溯 可以用出栈的办法
if not n :
return []
res = []
tmp = ""
brackets = ['(', ')']
left_num = 0
right_num = 0
def recursion(tmp_res: str, left_num: int, right_num: int):
if left_num == n and right_num == n:
res.append(tmp_res)
return
if left_num<n:
recursion(tmp_res +'(', left_num+1, right_num)
if right_num <n and left_num > right_num:
recursion(tmp_res +')', left_num, right_num+1)
recursion("", 0, 0)
return res
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
一开始的解法 没有问题 只是时间太长 做了很多的重复工作 想办法优化
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res = []
cur_depth = 0
def recursion(cur, tmp_res):
#print(cur, tmp_res)
if cur == n:
#print(tmp_res)
res.append(tmp_res)
return
tmp_list = ['.' for i in range(n)]
for i in range(n):
#需要剪枝 在进入之前 还是进入之后
tmp_list[i] = 'Q'
tmp_str = ''.join(tmp_list)
#tmp_res.append(tmp_str)
if judge(tmp_res+[tmp_str]) :
#进入下一层
recursion(cur+1, tmp_res+[tmp_str])
#恢复现场
tmp_list[i] = '.'
def judge(tmp):
#print(tmp)
info = []
dep = len(tmp)
for i in range(dep):
col = tmp[i].index('Q')
if len(info):
for tmpinfo in info:
if abs(i-tmpinfo[0]) == abs(col-tmpinfo[1]) or col ==tmpinfo[1] :
return False
tmp_info = [i, col]
info.append(tmp_info)
return True
recursion(0, [])
return res
queens = []#第i个位置表示第i行，queens[i]=j表示(i,j)有棋子。 直接在函数中进行判断，不需要每次都分析res的过去 保存
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res = []
#queens = []#第i个位置表示第i行，queens[i]=j表示(i,j)有棋子。
def recursion(cur, queens):
if cur == n:
res.append(queens[:])
return
for col in range(n):
flag = True
#需要剪枝 在进入之前 还是进入之后
queens.append(col)
#出现问题 是全部for循环 肯定会有置为flag false的
if cur >= 1:
for j in range(cur):
if queens[j] == col or cur - j ==abs(col - queens[j]):
flag = False
break
if flag:
recursion(cur + 1,queens)
queens.pop()
recursion(0, [])
#print(res)
t1 = []
for tmp in res:
t2 = []
for k in tmp:
tmp_list = ['.']*n
tmp_list[k] = 'Q'
tmp_str = ''.join(tmp_list)
t2.append(tmp_str)
t1.append(t2)
#print(t1)
return t1
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。
示例 1:
输入: n = 3, k = 3
输出: "213"
示例 2:
输入: n = 4, k = 9
输出: "2314"
自己一开始还是用的全排列的情况 然后直接找第k个 并且有剪枝 但是TLE 但记录自己的回溯法
class Solution:
def getPermutation(self, n: int, k: int) -> str:
res = ""
lis = [i for i in range(1,n+1)]
count = 0
flag = False
def recursion(tmp_res, tmp):
nonlocal res
nonlocal count
nonlocal flag
if flag:
return
if len(tmp_res) == n:
count += 1
if count == k:
#print(tmp_res)
res = ''.join([str(i) for i in tmp_res])
flag = True
return
for i in range(len(tmp)):
recursion(tmp_res+[tmp[i]], tmp[:i]+tmp[i+1:])
recursion([], lis)
return res
- 增加了剪枝操作 比较k和子树的大小 跳过很多子树
- used数组来保存 而不是原来的 对数组切片 传参
class Solution:
def getPermutation(self, n: int, k: int) -> str:
res = ""
lis = [i for i in range(1,n+1)]
factorial = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
used = [False for _ in range(n)]
flag = False
def recursion(tmp_res, k, used):
nonlocal flag
nonlocal res
ps = factorial[n-1-len(tmp_res)]
if len(tmp_res) == n and flag == False:
#print(tmp_res)
res = ''.join([str(i) for i in tmp_res])
flag = True
return
for i in range(n):
if used[i]:
continue
if k > ps:
k -= ps
continue
used[i] = True
recursion(tmp_res+[i+1], k, used)
recursion([], k, used)
#print(res)
return res
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
常规的解法，不过很有效的就是增加了一个剪枝 对i的循环范围的判断
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
lis = [i+1 for i in range(n)]
def recursion(cur_len, tmp_res, start):
if cur_len == k:
res.append(tmp_res[:])
return
#
for i in range(start, n - (k - cur_len) + 1):
tmp_res.append(lis[i])
recursion(cur_len+1, tmp_res, i + 1)
tmp_res.pop()
recursion(0, [], 0)
return res
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
其实是迷宫问题+ 二维平面的遍历搜索
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
#二维平面搜索问题
m = len(board)
if m == 0:
return False
n = len(board[0])
length = len(word)
marked =
#遍历二维平面的四个方向
directions = [(0, -1), (1, 0), (0, 1), (-1, 0)]
def judge(x, y, cur_len):
#print(x, y, cur_len)
#终止判断条件
if cur_len == length:
#print("test")
return True
for item in directions:
new_x = x + item[0]
new_y = y + item[1]
if 0 <= new_x < m and 0 <= new_y <n and not marked[new_x][new_y]:
#上面是前提条件的判断 保证下标不越界 保证不出现重复使用（走过的要有标记）
# 置位的位置 是直接置位还是 在判断相等之后再
if board[new_x][new_y] == word[cur_len]:
marked[new_x][new_y] = 1
# 注意和原先的不一样 这个在每次成功调用之后 一层一层的往回返回True 才能最终收到True的结果
if judge(new_x, new_y, cur_len+1):
return True
marked[new_x][new_y] = 0
return False
#出现问题 结果返回不对 没有返回值
for i in range(m):
for j in range(n):
if board[i][j] == word[0]:
#调用判断函数
# 注意在首位置上也要进行回溯 先标记后修改
marked[i][j] = 1
if judge(i, j, 1):
return True
marked[i][j] = 0
return False
更好的答案的方法：
class Solution:
#遍历二维平面的四个方向
directions = [(0, -1), (1, 0), (0, 1), (-1, 0)]
def exist(self, board: List[List[str]], word: str) -> bool:
#二维平面搜索问题
m = len(board)
if m == 0:
return False
n = len(board[0])
length = len(word)
marked = [[False for _ in range(n)] for _ in range(m)]
#出现问题 结果返回不对 没有返回值
for i in range(m):
for j in range(n):
if self.__search_word(board, word, 0, i, j, marked, m, n):
return True
return False
def __search_word(self, board, word, index, start_x, start_y, marked, m, n):
# 终止条件
if index == len(word) -1:
return board[start_x][start_y] == word[index]
# print(start_x, start_y)
# 当前匹配了 继续搜索
if board[start_x][start_y] == word[index]:
# 当前元素成功 先置为正确
marked[start_x][start_y] = True
for direction in self.directions:
new_x = start_x + direction[0]
new_y = start_y + direction[1]
if 0 <= new_x < m and 0 <= new_y < n and not marked[new_x][new_y] and self.__search_word(board, word,index + 1,
new_x, new_y,marked, m, n):
return True
# 当前元素的后续没有解 恢复现场
marked[start_x][start_y] = False
return False
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-ip-addresses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
细节内容比较多 注意看自己后面的出错情况
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
res = []
def recursion(tmp_res, tmp):
#print(tmp_res, tmp)
if len(tmp_res) == 4:
if not tmp:
res.append('.'.join(tmp_res))
return
elif not tmp:
return
lastused = -1
for i in range(1, 4):
#分别取1， 2， 3位数 做判断并加入 开始回溯
if i <= len(tmp):
tmp_num = int(tmp[:i])
if tmp_num > 255 :
continue
elif tmp_num == lastused:
continue
elif i> 1 and tmp[0] == '0':
continue
lastused = tmp_num
recursion(tmp_res+[tmp[:i]], tmp[i:])
recursion([], s)
return res
#几个出现的错误 1. 超出len 出现len为5 的情况 没有加好限定 2. 传的是list 注意tmp[:i] 切片的结果也是list
# 3. 结果出现重复-去重？ 使用lastused来维护 注意这是在一层while循环内部来比较 不需要考虑其他进入下一层的事情 是在比较兄弟节点是否相同
# 出现1111 int 原因是tmp为空 还在遍历list 增加一开始的限制
#4， 用的是 先append 再pop 则结果需要[:] 复制链表
# 出现 0000 错误 设置的lastused是 0
# "010010" 每段ip的要求不仅是0-255，同时每段不得有前置零，且不得删除任何一个数，即ip地址总长度不能变 #除去0开头，且长度大于1情况
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出: 5
解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
返回它的长度 5。
由最短序列想到应该是 BFS 然后这道题的关键在于 使用双端BFS来解决超时问题
最终修改版本 主要改动是变成了双向BFS 选择了分支小的那一侧来进行BFS遍历 即
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
wordList = set(wordList)
str_len = len(endWord)
head = {beginWord}
tail = {endWord}
tmp = list('abcdefghijklmnopqrstuvwxyz')
cur_len = 1
while head:
#关键点 在这 就是交换了首位逼近 通过首尾来互相逼近
if len(head) > len(tail):
head, tail = tail, head
next = set()
for cur in head :
for i in range(str_len):
for j in tmp:
#用这种方式来直接生成下一个next的内容
word = cur[:i] + j + cur[i+1:]
if word in tail:
return cur_len+1
if word in wordList:
next.add(word)
wordList.remove(word)
head = next
cur_len += 1
return 0
关于并查集 ： https://blog.csdn.net/liujian20150808/article/details/50848646#commentBox 给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
主要思想是反向思考： 从边界上的O点开始去试探，深度搜索，把能遍历到的O点置为# 最后再修改#-》O 详见代码
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if not board:
return
m = len(board)
n = len(board[0])
if m <= 2 or n <= 2 :
return
def search(x, y):
directions = [[-1, 0], [0, 1], [1, 0], [0,-1]]
for item in directions:
new_x = x + item[0]
new_y = y + item[1]
if 0 <= new_x <= m-1 and 0 <= new_y <= n-1:
if board[new_x][new_y] == 'O':
board[new_x][new_y] = '#'
search(new_x, new_y)
#由边界开始遍历
for j in range(0, n-1):
if board[0][j] == 'O':
board[0][j] = '#'
#开始进行搜索 置位
search(0, j)
for i in range(0, m-1):
if board[i][n-1] == 'O':
board[i][n-1] = '#'
search(i, n-1)
for j in range(1,n)[::-1]:
if board[m-1][j] == 'O':
board[m-1][j] = '#'
search(m-1, j)
for i in range(1, m)[::-1]:
if board[i][0] == 'O':
board[i][0] = '#'
search(i, 0)
#最后的修改
for i in range(0, m):
for j in range(0, n):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == '#':
board[i][j] = 'O'
return
回溯的思路 写起来更加方便快捷 python3 用回溯递归的方法去试探每一种可能性 对于一个字符串s，有len(s)种方法把它分成左右两个部分（分割方法看代码），假如左侧的不是回文，则舍弃这次尝试；假如左侧的是回文串，则把右侧的进行递归的分割，并返回右侧的分割的所有情况
class Solution:
def partition(self, s: str) -> List[List[str]]:
if not s:
return None
l = len(s)
if l == 1:
return [[s]]
res = []
def recursion(s, tmp):
if not s:
res.append(tmp)
return
for i in range(1, len(s)+1):
left = s[:i]
right = s[i:]
if left == left[::-1]:
recursion(right, tmp+[s[:i]])
recursion(s, [])
return res
一开始的做法 有动态规划 以及找规律的意思
class Solution:
def partition(self, s: str) -> List[List[str]]:
if not s:
return None
l = len(s)
if l == 1:
return [[s]]
if l == 2:
if s[0] == s[1]:
return [[s], [s[0], s[1]]]
else:
return [[s[0], s[1]]]
res = [[] for _ in range(l)]
for i in range(l):
if i == 0:
res[i] = [[s[0]]]
#每次递增的有在原来基础上直接相加的 还有自己尝试是否相等的
else:
#去做判断 尝试和前面的合并看是否是
for j in range(i)[::-1]:
if s[j:i+1] == s[j:i+1][::-1]:
#print(s[j:i+1])
#需要增加元素
#print(res[j-1])
if j == 0:
res[i].append([s[j:i+1]])
else:
for tmp in res[j-1]:
tmp1 = tmp + [s[j:i+1]]
res[i] += [tmp1]
res[i] += [item+ [s[i]] for item in res[i-1]]
#print(res[i])
return res[l-1]
思路很直接: 就是对每一个空着的格子穷举 1 到 9 找到一个合法的数字，则继续穷举下一个空格子。
要注意的就是： 只需要一个解，如何返回这个解 即对false 和 true的使用 何时返回 此时每一个其实都return了
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
# 算法思路十分单纯，就是对每一个空着的格子穷举 1 到 9 找到一个合法的数字，则继续穷举下一个空格子。
def backtrack(board, i, j):
m, n = 9, 9
# 遍历每一个格子 遇到最后一列则加一
if j == 9:
return backtrack(board, i+1, 0)
# 遇到最后一行0-8 是正常的 即遍历完成
if i == 9:
#print(board)
return True
# 正常格子
if board[i][j] != '.':
return backtrack(board, i, j+1)
# 遇到 空格开始 遍历
for k in range(1, 10):
tmp = str(k)
if isvalid(board, i, j, tmp):
board[i][j] = tmp
if backtrack(board, i, j+1):
return True
board[i][j] = '.'
# 不要忘记 每一个都会返回
return False
# def isvalid(board, i, j, k):
# now = k
# # 这是一行的判断
# if board[i].count(now) >= 1:
# return False
# # 列的判断
# for x in range(9):
# if board[x][j] == now :
# return False
# # 一个方框的判断
# tmp_i, tmp_j = i//3, j//3
# # print(tmp_i, tmp_j)
# tmp_list = []
# for x in range(tmp_i*3, tmp_i*3+3):
# for y in range(tmp_j*3, tmp_j*3+3):
# tmp_list.append(board[x][y])
# if now in tmp_list:
# return False
# return True
def isvalid(board, i, j, x):
for t in range(9):
# 这种队友一行一列的处理 值得学习
if board[t][j] == x: return False
if board[i][t] == x: return False
if board[i//3*3+ t//3][j//3*3+ t%3] == x: return False
return True
# def isvalid(board:List[List[str]],i:int,j:int,x:str) -> bool:
# for t in range(9):
# if board[t][j] == x:return False
# if board[i][t] == x:return False
# if board[i//3* 3 + t//3][j//3*3 + t%3] == x: return False
# return True
#print(board)
backtrack(board, 0, 0)