岛屿数量
给你一个由 '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
思路
用 DFS 去“淹掉”一个岛屿的所有陆地块，每当遇到一个新的“1”，就调用一次 DFS，把相邻陆地设为“0”，并且岛屿数加一。
Code
DFS:
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
count = 0
def dfs(a,b):
if grid[a][b] != "1":
return
grid[a][b] = "0"
if b>0:
dfs(a, b-1)
if n-b > 1:
dfs(a, b+1)
if m-a > 1:
dfs(a+1, b)
if a > 0:
dfs(a-1, b)
for a in range(m):
for b in range(n):
if grid[a][b] == "1":
dfs(a,b)
count+=1
return count腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值
0代表空单元格； - 值
1代表新鲜橘子； - 值
2代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
示例 1：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4
示例 2：
输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。
示例 3：
输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
想法梳理 + 优化
预处理阶段：
- 遍历整个网格，统计新鲜橘子的数量
fresh_count。 - 同时将所有腐烂橘子的位置加入队列
queue，作为 BFS 的起点。
👉 这里不需要一开始就判断某个新鲜橘子是否完全被隔离，因为 BFS 会自然处理到这一点。
BFS 腐烂传播过程：
- 使用 BFS，每轮代表“1分钟”，遍历队列中当前腐烂的橘子。
- 对它的上下左右 4 个方向的格子：
- 如果是新鲜橘子（值为 1），将其改为腐烂（设为 2），并加入队列。
- 同时
fresh_count -= 1。
- 每完成一轮（即当前层所有腐烂橘子处理完），时间 +1。
终止条件：
- 当队列为空时，检查
fresh_count：- 如果
fresh_count == 0，返回时间。 - 否则，返回
-1（说明有新鲜橘子无法被腐烂）。
- 如果
小细节提醒：
- 可以用队列
collections.deque实现高效的 BFS。 - 每一轮 BFS 都要记录当前队列大小（即当前层腐烂橘子的数量），作为本轮腐烂传播的“起点数”。
- 时间计数可以在每一轮后
time += 1，但要注意如果一开始就没有新鲜橘子应该直接返回 0。
Code:
from collections import deque
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
fresh_count = 0
queue = deque()
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
fresh_count += 1
if grid[i][j] == 2:
queue.append((i,j))
directions = [(1,0), (-1,0), (0,1), (0,-1)]
minute = 0
while queue and fresh_count > 0:
for _ in range(len(queue)):
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = (x + dx), (y + dy)
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny]==1:
grid[nx][ny] = 2
fresh_count -= 1
queue.append((nx,ny))
minute += 1
return minute if fresh_count == 0 else -1
时间和空间复杂度分析
- 时间复杂度：O(m × n)，每个格子最多只访问一次。
- 空间复杂度：O(m × n)，最坏情况下所有橘子都进队列。
课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
这道题的本质是一个图的拓扑排序问题，可以抽象成：
✅ 问题建模
- 每门课程是图中的一个节点。
- 每个先修关系
[a, b]表示一条边：b → a。 - 如果这个有向图中存在 环，说明有课程循环依赖，无法完成全部课程。
- 如果图是 无环有向图（DAG），说明课程是有序的，可以按某种顺序完成全部课程。
✅ 检测有向图是否有环的常见方法：
1. Kahn’s 算法（BFS 拓扑排序）：
- 统计每个节点的入度；
- 每次找入度为 0 的节点，移除并更新它指向的节点的入度；
- 如果最终处理的节点数量 < 总课程数，说明存在环。
2. DFS + 访问状态标记：
- 对每个节点进行 DFS，使用状态数组记录访问状态：
- 0：未访问
- 1：访问中（当前 DFS 路径中）
- 2：访问完成
- 如果在 DFS 中再次遇到访问中的节点（状态为 1），说明出现环。
Code: DFS
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
visited = [0] * numCourses
pre = defaultdict(list)
for a, b in prerequisites:
pre[b].append(a)
def dfs(course):
if visited[course] == 1:
return False
elif visited[course] == 2:
return True
visited[course] = 1
for neighbor in pre[course]:
if not dfs(neighbor):
return False
else:
visited[course] = 2
return True
for course in range(numCourses):
if not dfs(course):
return False
return Truegraph[b].append(a) 表示 b 是 a 的前置课。
DFS 中状态判断逻辑：
1是“当前路径正在访问”，用于检测环。2是“访问完成”，可直接跳过。
DFS 过程中一旦发现环，立即返回 False。
对所有课程都进行 DFS 避免遗漏不连通图部分。
复杂度分析：
- 时间复杂度：O(V + E)，其中 V 是课程数，E 是先修边数。
- 空间复杂度：O(V + E)，用于图的邻接表和递归栈。
实现 Trie (前缀树)
Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串word。boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
示例：
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
Trie 树结构思路整理
基本结构设计
- 每个节点用
Node类表示，包含两个成员：son: 一个字典，key 是字符，value 是子节点。end: 一个布尔值，表示是否是某个单词的结尾。
Trie 类设计
- 使用一个
root节点作为前缀树的起点。 - 提供三个核心方法：
insert,search,startsWith。
方法功能与思路
insert(word)
- 从
root开始，逐字符遍历word。 - 如果当前字符在当前节点的
son中不存在，创建新的子节点。 - 最后将最后一个字符节点的
end标记为True。
search(word)
- 同样从
root开始，逐字符查找。 - 如果路径中有字符不存在于
son中，直接返回False。 - 如果路径存在，则返回最后一个节点的
end值，判断是否为完整单词。
startsWith(prefix)
- 类似于
search，但不关心最后一个字符是否为单词结束。 - 只要路径完整存在，说明前缀存在。
Code:
class Node:
def __init__(self):
self.son = {}
self.end = False
class Trie:
def __init__(self):
self.root = Node()
def insert(self, word: str) -> None:
cur = self.root
for s in word:
if s not in cur.son:
cur.son[s] = Node()
cur = cur.son[s]
cur.end = True
def search(self, word: str) -> bool:
cur = self.root
for s in word:
if s not in cur.son:
return False
cur = cur.son[s]
return True if cur.end else False
def startsWith(self, prefix: str) -> bool:
cur = self.root
for s in prefix:
if s not in cur.son:
return False
cur = cur.son[s]
return True时间与空间复杂度
- 时间复杂度：
insert,search: O(n)，n 是字符串长度。startsWith: O(m)，m 是前缀长度。
- 空间复杂度：
- 最坏情况下插入 N 个长度为 L 的互不相同单词，需要 O(N×L) 空间。