leetcode题目按类型
深度优先搜索DFS+递归
dfs（回溯）算法框架
-
**核心**
：for循环里面的递归，在递归调用之前做选择，在调用之后撤销选择。
- 3个问题：
- 路径：已经做的选择
- 选择列表：当前可做的选择
- 结束条件：到达决策树底层，无法再做选择的条件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def backtrack(选择列表, path):
if 满足结束条件:
result.add(path)
return
for 选择 in 选择列表:
path.append(选择)
backtrack(选择列表, path)
path.pop()
result = []
path = []
backtrack(选择列表, path)
return result
- 带有visited的dfs框架：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def DFS(选择列表, path):
if 满足结束条件:
result.add(path)
return
visited.add(start)
for 选择 in 选择列表:
path.append(选择)
backtrack(选择列表, path)
path.pop()
visited.remove(start)
visited = set()
result = []
path = []
DFS(选择列表, path)
return result
二叉树的dfs（路径总和2）
- 选择只有左子树和右子树
- 无需 visited
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def dfs(root, targetSum):
if not root:
return # 注意 return
path.append(root.val) # 添加路径
targetSum -= root.val
if not root.left and not root.right and targetSum == 0: # 如果满足条件
res.append(path[:])
dfs(root.left, targetSum)
dfs(root.right, targetSum)
path.pop() # 注意要 去掉路径
res = []
path = []
dfs(root,targetSum)
return res
✅ 46. 全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
1
输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
✅（5m）
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def helper(path, nums):
if len(path) == len(nums):
res.append(path)
for i in nums:
if i not in path:
helper(path+[i], nums)
res = []
path = []
helper(path, nums)
return res
总结：
- 在basecase里，注意，满足条件了就要return出去
- 组合问题需要做选择前添加判断，跳过不满足条件的选择
✅(20m)79. 单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
1
# 示例board =[ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']]给定 word = "ABCCED", 返回 true给定 word = "SEE", 返回 true给定 word = "ABCB", 返回 false
✅（20m）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
def exist(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 、动态规划、回溯法、递归之间的关系是什么？
回溯搜索是深度优先搜索（DFS）的一种。对于某一个搜索树来说（搜索树是起记录路径和状态判断的作用），回溯和DFS，其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。为了减少存储空间，在深度优先搜索中，用标志的方法记录访问过的状态，这种处理方法使得深度优先搜索法与回溯法没什么区别了。
递归就是自我调用，经常作为一种编程的实现方式，比如题主问题中的DFS 、动态规划、回溯法都可以用递归来实现，当然也可以用非递归来实现。很多时候一个概念也可以用递归的方式来定义（比如gnu）。
回溯是一种通用的算法，把问题分步解决，在每一步都试验所有的可能，当发现已经找到一种方式或者目前这种方式不可能是结果的时候，退回上一步继续尝试其他可能。很多时候每一步的处理都是一致的，这时候用递归来实现就很自然。
深度优先搜索是当回溯用于树的时候。当然了，几乎所有可以用回溯解决的问题都可以表示为树。那么这俩在这里就几乎同义了。如果一个问题解决的时候显式地使用了树，那么我们就叫它dfs。很多时候没有用树我们也管它叫dfs严格地说是不对的，但是dfs比回溯打字的时候好输入。别的回答里提到了砍枝，实际上这二者都可以砍枝。
动态规划，回溯可以用于所有用穷举法可以解决的问题，而DP只用于**具有最优子结构的问题**。所以不是所有问题都适合用dp来解决，比如八皇后。dp需要存贮子问题的解，回溯不需要。
回溯算法
- 深度优先遍历的特有的现象，节约空间
全排列思路：
在枚举第一位的时候，有 3 种情况。
在枚举第二位的时候，前面已经出现过的数字就不能再被选取了；
在枚举第三位的时候，前面 2 个已经选择过的数字就不能再被选取了。
第 1 步都是先画图，画图是非常重要的，只有画图才能帮助我们想清楚递归结构，想清楚如何剪枝
步骤，即在画图的过程中思考清楚：
1、分支如何产生；
2、题目需要的解在哪里？是在叶子结点、还是在非叶子结点、还是在从跟结点到叶子结点的路径？
3、哪些搜索是会产生不需要的解的？例如：产生重复是什么原因，如果在浅层就知道这个分支不能产生需要的结果，应该提前剪枝，剪枝的条件是什么，代码怎么写？
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
数组深拷贝、浅拷贝
1
res.append(path[:]) # 注意相当于这里做一次拷贝。否则输出为全空
1
# 浅拷贝, 指向同一地址a = [2,3,34,4]b = aa.append(222)a, b
1
# 深拷贝， 不同地址a = [2,3,34,4]b = a[:]c = list(a)d = a*1import copye = copy.copy(a)a.append(222)a, b, c, d, e
步骤
- 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。
- 当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。
- 如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
概括
深度优先搜索的步骤分为
- 递归下去
- 回溯上来。
顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标。这里称之为递归下去。
否则既没有达到目标又无路可走了，那么则退回到上一步的状态，走其他路。这便是回溯上来。
———————————-
🚩(20m) 101. 对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
1
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1 / \ 2 2 \ \ 3 3 进阶：你可以运用递归和迭代两种方法解决这个问题吗？
2️⃣使用递归的思想
如果同时满足下面的条件，两个树互为镜像：
- 它们的两个根结点具有相同的值
- 每个树的右子树都与另一个树的左子树镜像对称
1
# guanjieclass Solution: def isSymmetric(self, root: TreeNode) -> bool: if not root: return return self.check(root.left, root.right) def check(self, left, right): if left is None and right is None: return True if left is None or right is None: return False if left.val != right.val : return False return self.check(left.left, right.right) and self.check(left.right, right.left)
🚩(60m) 394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
1
示例 1：输入：s = "3[a]2[bc]"输出："aaabcbc"示例 2：输入：s = "3[a2[c]]"输出："accaccacc"示例 3：输入：s = "2[abc]3[cd]ef"输出："abcabccdcdcdef"示例 4：输入：s = "abc3[cd]xyz"输出："abccdcdcdxyz"
2️⃣栈和递归使用
1
class Solution: def decodeString(self, s: str) -> str: def dfs(i): res, multi = "", 0 while i<len(s): if '0' <= s[i] <= '9': multi = multi*10 + s[i] elif s[i] == '[': # 注意，返回i的含义是更新上层递归指针位置，因为内层递归已经吃掉一串str，若不跟新i， # 外层仍然从i+1开始，则会重复处理内层处理过的一串str。 i, tmp = dfs(i+1) res += multi * tmp multi = 0 elif s[i] == ']': return i,res else: res += s[i] i+=1 return res return dfs(0)
🚩105. 从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
1
前序遍历 preorder = [3,9,20,,7]中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树： 3 / \ 9 20 / \ 15 7
2️⃣
1
class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: # def helper(): if not preorder: return None root = TreeNode(preorder[0]) mid = inorder.index(preorder[0]) root.left = self.buildTree(preorder[1:mid+1], inorder[:mid]) # 主要要+1 root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:]) return root
🚩114. 二叉树展开为链表
给定一个二叉树，原地将它展开为一个单链表。
1
例如，给定二叉树 1 / \ 2 5 / \ \3 4 6将其展开为：1 \ 2 \ 3 \ 4 \ 5 \ 6
1
# 前序遍历class Solution: def flatten(self, root: TreeNode) -> None: """ Do not return anything, modify root in-place instead. """ if root.left: root.next = root.left elif root.right: root.next = flatten(root.left)
🚩（困难）679. 24 点游戏
你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。
1
示例 1:输入: [4, 1, 8, 7]输出: True解释: (8-4) * (7-1) = 24示例 2:输入: [1, 2, 1, 2]输出: False注意:除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。
1
class Solution: def judgePoint24(self, nums: List[int]) -> bool: for i in range(4): if def dfs(nums, depth):
1
from typing import Listnums = [4, 1, 8, 7]solution = Solution()result = solution.judgePoint24(nums)result
✅(20m)79. 单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
1
# 示例board =[ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']]给定 word = "ABCCED", 返回 true给定 word = "SEE", 返回 true给定 word = "ABCB", 返回 false
④
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
def exist(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
2️⃣
✅ (20m) 46. 全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
1
输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
2️⃣
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
if depth == size:
res.append(path[:])
return
for i in range(size):
if not used[i]:
used[i] = True
path.append(nums[i])
dfs(nums, size, depth+1, path, used, res)
used[i] = False
path.pop()
size = len(nums)
if size == 0:
return []
used = [False for _ in range(size)]
res = []
dfs(nums, size, 0, [], used, res)
return res
1
from typing import Listnums = [1,2,4]solution = Solution()result = solution.permute(nums)result
3️⃣
1
class Solution: def __init__(self): self.result = [] def permute(self, nums: List[int]) -> List[List[int]]: def permute_sub(nums,path): if len(path) == len(nums): self.result.append(path[:]) for num in nums: if num not in path: path.append(num) # 做选择 permute_sub(nums,path) # 递归 path.pop() # 撤销选择 permute_sub(nums,[]) return self.result
④
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def helper(path, nums):
if len(path) == len(nums):
res.append(path)
for i in nums:
if i not in path:
helper(path+[i], nums)
res = []
path = []
helper(path, nums)
return res
总结：
- 在basecase里，注意，满足条件了就要return出去
- 组合问题需要做选择前添加判断，跳过不满足条件的选择
✅(60m) 51. N 皇后
难度困难725
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
1
2
3
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
1
2
输入：n = 1
输出：[["Q"]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def __init__(self):
self.result = []
def solveNQueens(self, n: int) -> List[List[str]]:
def solveNQueens_sub(n, path, diagonal1, diagonal2):
if len(path) == n:
self.result.append(path[:])
for num in range(n):
if num not in path and len(path) - num not in diagonal1 and len(path) + num not in diagonal2:
diagonal1.add(len(path) - num)
diagonal2.add(len(path) + num)
path.append(num) # 做选择
solveNQueens_sub(n,path,diagonal1,diagonal2) # 递归
path.pop() # 撤销选择
diagonal1.remove(len(path) - num) # 注意长度要是当前的长度，和上面的add保持一致
diagonal2.remove(len(path) + num)
diagonal1, diagonal2 = set(), set() # 用set定义更容易，复杂度比较低，为O(log(n))
solveNQueens_sub(n,[],diagonal1,diagonal2)
self.result.sort()
return [["."*index + "Q" + (n-index-1)*"." for index in path] for path in self.result]
总结：
-
查找时可以考虑用 $set$，定义更容易，复杂度比较低，为$O(log(n))$。虽然 $dict$复杂度为 $O(1)$，但是由于有哈希化的过程，所以时间通常也没有少。
-
注意回溯前后，长度要是当前的长度，和上面的add保持一致
1 2 3 4 5 6 7
diagonal1.add(len(path) - num) diagonal2.add(len(path) + num) path.append(num) # 做选择 solveNQueens_sub(n,path,diagonal1,diagonal2) # 递归 path.pop() # 撤销选择 diagonal1.remove(len(path) - num) # 注意长度要是当前的长度，和上面的add保持一致 diagonal2.remove(len(path) + num)
🚩(30m)78. 子集
难度中等995
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
1
2
输入：nums = [0]
输出：[[],[0]]
1
class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: def backtrack(nums,start,track): res.append(track[:]) for i in range(start,len(nums)): # 从start开始可以避免重复 track.append(nums[i]) backtrack(nums,i+1,track) track.pop() res = [] track = [] backtrack(nums,0,track) return res
✅(40m)77. 组合
难度中等499
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例:
1
2
3
4
5
6
7
8
9
10
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
总结：
- 回溯算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def backtrack(start,path):
if len(path) == k:
print(path)
result.append(path[:])
for i in range(start,n+1):
path.append(i)
backtrack(i+1,path) # 注意这里是i+1
path.pop()
result = []
path = []
backtrack(1,path)
return result
- 注意开始的位置：
backtrack(i+1,path) # 注意这里是i+1， 这样才能保证每次都比当前大。
🚩 22. 括号生成
难度中等1566
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
1
2
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
1
2
输入：n = 1
输出：["()"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def backtrack(left,right,track,res):
if left<0 or right<0:
return
if right < left:
return
if left==0 and right ==0:
res.append(track)
return
backtrack(left-1,right,track+'(',res)
backtrack(left,right-1,track+')',res)
if n==0:
return {}
res = []
track = ""
backtrack(n,n,track,res)
return res
🚩(30m) 17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例:
1
2
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
2️⃣
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def letterCombinations(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']}
def backtrack(conbination,nextdigit):
if len(nextdigit) == 0:
res.append(conbination)
else:
for letter in phone[nextdigit[0]]:
backtrack(conbination + letter,nextdigit[1:])
res = []
backtrack('',digits) # 路径， 选择
return res
🚩(30m) 100. 相同的树
难度简单634收藏分享切换为英文接收动态反馈
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if not p and not q:
return True
elif not p or not q :
return False
elif p.val != q.val:
return False
else:
return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
🚩(20m) 112. 路径总和
难度简单600收藏分享切换为英文接收动态反馈
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
1
2
3
4
5
6
7
8
9
class Solution:
def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
if not root:
return False # 注意要return false！！！，因为是or
targetSum -= root.val
if not root.left and not root.right:
return targetSum == 0
return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)
1
2
if not root:
return False # 注意要return false！！！，因为是or
🚩(30m) 113. 路径总和 II
难度中等508收藏分享切换为英文接收动态反馈
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
res = []
path = []
def dfs(root, targetSum):
if not root:
return # 注意 return
path.append(root.val) # 添加路径
targetSum -= root.val
if not root.left and not root.right and targetSum == 0:
res.append(path[:])
dfs(root.left, targetSum)
dfs(root.right, targetSum)
path.pop() # 注意要 去掉路径
dfs(root,targetSum)
return res
✅(30m) 129. 求根节点到叶节点数字之和
难度中等367收藏分享切换为英文接收动态反馈
给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
- 例如，从根节点到叶节点的路径
1 -> 2 -> 3表示数字123。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
def dfs(root, path, res):
if not root:
return
path = path*10 + root.val
# print(path)
if not root.left and not root.right:
res.append(path)
dfs(root.left, path, res)
dfs(root.right, path, res)
path //= 10
res = [] # 注意要把res定义成数组，才会才传参的过程改变
path = 0
dfs(root, path, res)
return sum(res)
注意要把res定义成数组，才会才传参的过程改变
(30m) 🚩 222. 完全二叉树的节点个数
难度中等504收藏分享切换为英文接收动态反馈
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
