目录
一、栈和深度优先搜索
二、栈和 DFS
三、DFS - 模板 I
三、岛屿数量
3.1 题目要求
3.2 解决过程
四、克隆图
4.1 题目要求
4.2 解决过程
五、目标和
5.1 题目要求
5.2 解决过程
六、DFS - 模板 II
七、二叉树的中序遍历
7.1 题目要求
7.2 解决过程
树的遍历：https://blog.csdn.net/qq_39478403/article/details/107329233
参考文献：https://leetcode-cn.com/leetbook/read/queue-stack/k3beh/
参考文献：https://leetcode-cn.com/leetbook/read/queue-stack/gro21/
// Java /* * Return true if there is a path from cur to target. */ boolean DFS(Node cur, Node target, Set<Node> visited) { return true if cur is target; for (next : each neighbor of cur) { if (next is not in visited) { add next to visted; return true if DFS(next, target, visited) == true; } } return false; }
参考文献：https://leetcode-cn.com/leetbook/read/queue-stack/gp5a7/
法一：BFS 迭代实现。沿竖直和水平方向遍历输入矩阵，每发现一个陆地 (标号1)，就对其进行 BFS，并将可由 BFS 访问/搜索到的陆地都置为已访问/已搜索 (标号0) 以表示属于同一个岛屿，且因为已访问/已搜索而不必在后续过程中再次访问/搜索 (意为不会访问同一个节点两次)。空间复杂度 O(n)，时间复杂度 O(n)。
2020/09/02 - 70.26% (80ms)
class Solution: def numIslands(self, grid: List[List[str]]) -> int: land_nums = 0 # 岛屿数量 for row in range(len(grid)): # 遍历行 for col in range(len(grid[0])): # 遍历列 if grid[row][col] == '1': # 发现陆地 land_nums += 1 # 岛屿数量 +1 grid[row][col] = '0' # 将已访问/已探索的陆地置为 0, 以后便不必再重复访问/搜索 # 对已发现陆地通过 BFS 扩张/辐射, 将与之相邻的陆地都标记为已访问/已探索状态 land_positions = collections.deque() # 内置双端队列, 保存已访问/已探索相邻陆地坐标 land_positions.append([row, col]) # 当前已访问/已探索陆地坐标入队 while len(land_positions) > 0: # 只要当前队列中还保存有已访问/已探索陆地坐标 x, y = land_positions.popleft() # 出队探索 for new_x, new_y in [[x, y+1], [x, y-1], [x+1, y], [x-1, y]]: # 向 4 个方向扩张/辐射 # 判断有效性, 要求是坐标界限范围内的陆地 if (0 <= new_x < len(grid)) and (0 <= new_y < len(grid[0])) and (grid[new_x][new_y] == '1'): grid[new_x][new_y] = '0' # 因为可由 BFS 访问到, 故属同一块岛，将其置 0 代表已访问/已探索 land_positions.append([new_x, new_y]) # 已访问/已探索陆地坐标入队 return land_nums法一改：BFS 迭代实现 - 函数封装。空间复杂度 O(n)，时间复杂度 O(n)。
2020/09/02 - 70.26% (80ms)
class Solution: def numIslands(self, grid: List[List[str]]) -> int: from collections import deque # 双端队列 if not grid: return 0 row = len(grid) # 行数 col = len(grid[0]) # 列数 cnt = 0 # 岛屿数 def bfs(i, j): queue = deque() # 保存已访问/已探索的陆地队列 grid[i][j] = "0" # 将已发现的陆地置为已访问/已探索状态 0 queue.appendleft((i, j)) # 已发现陆地坐标入队 while queue: # 只要队列中还有坐标 i, j = queue.pop() # 弹出一个坐标 for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]: # 向周围 4 个方向以单位距离搜索 tmp_i = i + x tmp_j = j + y # 若在范围内发现新陆地 if (0 <= tmp_i < row) and (0 <= tmp_j < col) and (grid[tmp_i][tmp_j] == "1"): grid[tmp_i][tmp_j] = "0" # 将已发现的陆地置为已访问/已探索状态 0 queue.appendleft((tmp_i, tmp_j)) # 已发现陆地坐标入队 # 遍历所有元素 for i in range(row): for j in range(col): if grid[i][j] == "1": # 若发现新陆地 bfs(i, j) # 进行 BFS cnt += 1 # 岛屿数 +1 return cnt法二：DFS 递归实现。抛开陆地、岛屿和水等概念，该问题的实质是：求一个只含 0/1 元素的矩阵中，元素为 1 的连通区域个数，如图所示：
为此，使用 DFS 的解决过程可表述为：
建立一个已访问/已探索数组 (visited array) 以记录某位置是否被访问/探索过 (的状态)；对于一个未被访问过且元素为 1 的位置，递归进入其上下左右元素为 1 之处，将其 visited 置为 true；重复上述过程；遍历完相邻区域后，令结果 cnt +1，然后继续搜素下一个被访问过且元素为 1 的位置，直至遍历完整个矩阵。但本题目仅要求计算元素为 1 的连通区域个数，因此无需额外空间存储 visited 信息。此外，上述过程不会对元素为 0 的位置进行操作，故对于已访问/已探索的位置，将其元素置 0 即可，以节省 visited 信息的存储开销。空间复杂度 O(n)，时间复杂度 O(n)。
2020/09/02 - 57.76% (84ms)
class Solution: def numIslands(self, grid: List[List[str]]) -> int: if not grid: return 0 row = len(grid) # 行数 col = len(grid[0]) # 列数 cnt = 0 # 岛屿数 def dfs(i, j): grid[i][j] = "0" # 将已发现的陆地置为已访问/已探索状态 0 for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]: # 向周围 4 个方向以单位距离搜索 tmp_i = i + x tmp_j = j + y # 若在范围内发现新陆地 if (0 <= tmp_i < row) and (0 <= tmp_j < col) and (grid[tmp_i][tmp_j] == "1"): dfs(tmp_i, tmp_j) # 递归进行 DFS # 遍历所有元素 for i in range(row): for j in range(col): if grid[i][j] == "1": # 若发现新陆地 dfs(i, j) # 进行 DFS cnt += 1 # 岛屿数 +1 return cnt法二改：DFS 递归实现。空间复杂度 O(n)，时间复杂度 O(n)。
2020/09/02 - 81.81% (76ms)
class Solution: def dfs(self, grid, i, j): # 等价的有效性条件 if (i < 0) or (j < 0) or (i >= len(grid)) or (j >= len(grid[0])) or (grid[i][j] != '1'): return else: # 若在范围内发现新陆地 (元素为1) grid[i][j] = '0' # 将已发现的陆地置为已访问/已探索状态 0 # 然后往上下左右4个方向依次进行递归 DFS self.dfs(grid, i+1, j) # 右 self.dfs(grid, i-1, j) # 左 self.dfs(grid, i, j+1) # 下 self.dfs(grid, i, j-1) # 上 def numIslands(self, grid: List[List[str]]) -> int: if not grid: return 0 cnt = 0 # 岛屿数 # 遍历所有元素 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == '1': # 若发现新陆地 self.dfs(grid, i, j) # 进行 DFS cnt += 1 # 岛屿数 +1 return cnt法三：并查集。
2020/09/02 - 20.64% (108ms)
class Solution: def numIslands(self, grid: List[List[str]]) -> int: f = {} def find(x): # Python 字典 setdefault() 函数和 get()方法 类似, 若键不存在于字典中，将会添加键并将值设为默认值 f.setdefault(x, x) if f[x] != x: f[x] = find(f[x]) return f[x] def union(x, y): f[find(x)] = find(y) if not grid: return 0 row = len(grid) col = len(grid[0]) for i in range(row): for j in range(col): if grid[i][j] == "1": for x, y in [[-1, 0], [0, -1]]: tmp_i = i + x tmp_j = j + y if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == "1": union(tmp_i * row + tmp_j, i * row + j) # print(f) res = set() for i in range(row): for j in range(col): if grid[i][j] == "1": res.add(find((i * row + j))) return len(res)小贴士：
问：已经有 BFS 了，为什么还要有 DFS ？
答：BFS 可以找到最短距离，但 空间复杂度高；而 DFS 的空间复杂度则相对较低。因此，使用 BFS 需要付出一定代价。通常，寻找最短路径时会使用 BFS，其他情况则更多会使用 DFS (递归代码相对好写)。
参考文献
https://leetcode-cn.com/problems/number-of-islands/solution/dfs-bfs-bing-cha-ji-chao-ji-qing-xi-by-powcai/
https://leetcode-cn.com/problems/number-of-islands/solution/xiong-mao-shua-ti-python3-yi-jiu-shi-bfsmo-ban-ti-/
https://leetcode-cn.com/problems/number-of-islands/solution/pythonjavascript-tao-lu-dfs200-dao-yu-shu-liang-by/
个人实现
法一：DFS 递归实现。图的遍历基于树的遍历，但又更复杂些。空间复杂度 O(n)，时间复杂度 O(n)。
2020/09/02 - 97.98% (40ms) - 最佳
""" # Definition for a Node. class Node: def __init__(self, val = 0, neighbors = []): self.val = val self.neighbors = neighbors """ class Solution: def __init__(self): self.seen = {} # 已访问哈希表 def cloneGraph(self, node: 'Node') -> 'Node': if not node: # 空节点处理 return node if node in self.seen: # 已访问节点可直接索引并返回 return self.seen[node] new = Node(node.val) # 克隆当前节点 self.seen[node] = new # 当前节点加入已访问哈希表 for n in node.neighbors: new.neighbors.append(self.cloneGraph(n)) # 遍历以添加邻接节点 return new # 返回当前节点官方实现与说明
# 同个人实现法一 class Solution(object): def __init__(self): self.visited = {} def cloneGraph(self, node): if not node: return node # 如果该节点已经被访问过了，则直接从哈希表中取出对应的克隆节点返回 if node in self.visited: return self.visited[node] # 克隆节点，注意到为了深拷贝我们不会克隆它的邻居的列表 clone_node = Node(node.val, []) # 哈希表存储 self.visited[node] = clone_node # 遍历该节点的邻居并更新克隆节点的邻居列表 if node.neighbors: clone_node.neighbors = [self.cloneGraph(n) for n in node.neighbors] return clone_node
2020/09/02 - 93.11% (44ms)
class Solution: def cloneGraph(self, node: 'Node') -> 'Node': if not node: return node # 已访问节点哈希表 visited = {} # 将题目给定的节点添加到队列 queue = collections.deque([node]) # 克隆第一个节点并存储到哈希表中 visited[node] = Node(node.val) # 广度优先搜索 while queue: # 取出队列的头节点 n = queue.popleft() # 遍历该节点的邻居 for neighbor in n.neighbors: if neighbor not in visited: # 如果没有被访问过，就克隆并存储在哈希表中 visited[neighbor] = Node(neighbor.val) # 将邻居节点加入队列中 queue.append(neighbor) # 更新当前节点的邻居列表 visited[n].neighbors.append(visited[neighbor]) return visited[node]
2020/09/02 - 93.11% (44ms)
参考文献
https://leetcode-cn.com/leetbook/read/queue-stack/gmcr6/
https://leetcode-cn.com/problems/clone-graph/solution/ke-long-tu-by-leetcode-solution/
https://leetcode-cn.com/problems/clone-graph/solution/ke-long-tu-by-leetcode-solution/541746
测试用例
[1,1,1,1,1] 3 [38,21,23,36,1,36,18,3,37,27,29,29,35,47,16,0,2,42,46,6] 14 [14,23,35,48,10,39,34,40,36,45,11,14,41,6,4,17,42,22,0,35] 44失败测试
法一：递归。相当于暴力法了。空间复杂度 O(2^n)，时间复杂度 O(2^n)。
2020/09/03 - 超出时间限制
class Solution: def findTargetSumWays(self, nums: List[int], S: int) -> int: def dfs(index, s): if index == length: return 1 if s == 0 else 0 return dfs(index+1, s+nums[index]) + dfs(index+1, s-nums[index]) length = len(nums) return dfs(0, S)其他实现与说明
class Solution: def findTargetSumWays(self, nums: List[int], S: int) -> int: def dfs(cur, i, d): if (i < len(nums)) and ((cur, i) not in d): # 搜索周围节点 # key：cur - 目前的和, i - 目前的位数 # value：该元组推导到最后的解数目 d[(cur, i)] = dfs(cur+nums[i], i+1, d) + dfs(cur-nums[i], i+1, d) # radiansdict.get(key, default=None), 若键不在字典中返回 default 默认值 return d.get((cur, i), int(cur == S)) # 和为 S 返回 1, 否则返回 0 d = {} return dfs(0, 0, d)
2020/09/03 - 41.49% (504ms)
class Solution: def findTargetSumWays(self, nums: List[int], S: int) -> int: if (sum(nums) < S) or ((sum(nums) + S) % 2 == 1): return 0 P = (sum(nums) + S) // 2 dp = [1] + [0 for _ in range(P)] for num in nums: for j in range(P, num-1, -1): dp[j] += dp[j-num] return dp[P] class Solution: def findTargetSumWays(self, nums: List[int], S: int) -> int: summ = sum(nums) ## changed if (summ < S) or ((summ + S) % 2 == 1): return 0 P = (summ + S) // 2 dp = [1] + [0] * P ## changed for num in nums: for j in range(P, num-1, -1): dp[j] += dp[j-num] return dp[P]
2020/09/03 - 99.42% (72ms) - 最佳
class Solution: def findTargetSumWays(self, nums: List[int], S: int) -> int: length = len(nums) dp = {(0,0): 1} for i in range(1, length+1): for j in range(-sum(nums), sum(nums) + 1): dp[(i,j)] = dp.get((i - 1, j - nums[i-1]), 0) + dp.get((i - 1, j + nums[i-1]), 0) return dp.get((length, S), 0) class Solution: def findTargetSumWays(self, nums, S): length, dp = len(nums), {(-1,0): 1} for i in range(0, length): for j in range(-sum(nums), sum(nums) + 1): dp[(i,j)] = dp.get((i - 1, j - nums[i]), 0) + dp.get((i - 1, j + nums[i]), 0) return dp.get((length-1, S), 0)
2020/09/03 - 5.09% (1572ms)
参考文献
https://leetcode-cn.com/leetbook/read/queue-stack/ga4o2/
https://leetcode-cn.com/problems/target-sum/solution/mu-biao-he-by-leetcode/
https://leetcode-cn.com/problems/target-sum/solution/python-dfs-xiang-jie-by-jimmy00745/
参考文献：https://leetcode-cn.com/leetbook/read/queue-stack/g2g9c/
个人实现
法一：递归。
2020/07/14 - 99.15% - 最优
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: def traverse(node): if node: traverse(node.left) # 先左子节点 result.append(node.val) # 再根节点 traverse(node.right) # 最后右子节点 result = [] traverse(root) return result法二：迭代。
2020/07/14 - 87.96% - 次优
class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: stack = [] result = [] # 遍历结果列表 node = root # 树根节点指针 while node or stack: if node: stack.append(node) # 这里要加入的是树, 不是树的值 node = node.left else: node = stack.pop() result.append(node.val) # 遍历结果记录 node = node.right # 左子节点寻找完毕 return result参考文献
https://leetcode-cn.com/leetbook/read/queue-stack/gnq5i/
