题目列表
200. 岛屿数量 中等难度 leetcode链接
994. 腐烂的橘子 中等难度 leetcode链接
226. 翻转二叉树 简单难度 leetcode链接
208. 实现Trie（前缀树） 中等难度 leetcode链接
题目
（1）岛屿数量
题目
给你一个由 '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.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]的值为'0'或'1'
思考
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"
for x, y in [[-1, 0], [1, 0], [0, -1], [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":
dfs(tmp_i, tmp_j)
for i in range(row):
for j in range(col):
if grid[i][j] == "1":
dfs(i, j)
cnt += 1
return cnt （2）腐烂的橘子
题目
在给定的 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 。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j]仅为0、1或2
思考
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
# 广度优先遍历
# 时间复杂度：O(nm)。即进行一次广度优先搜索的时间，其中 n,m 分别为 grid 的行数与列数。
# 空间复杂度：O(nm)。需要额外的 dis 数组记录每个新鲜橘子被腐烂的最短时间，大小为 O(nm)，且广度优先搜索中队列里存放的状态最多不会超过 nm 个，最多需要 O(nm) 的空间，所以最后的空间复杂度为 O(nm)。
R, C = len(grid), len(grid[0])
# queue - all starting cells with rotting oranges
queue = collections.deque()
for r, row in enumerate(grid):
for c, val in enumerate(row):
if val == 2:
queue.append((r, c, 0))
def neighbors(r, c) -> (int, int):
for nr, nc in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
if 0 <= nr < R and 0 <= nc < C:
yield nr, nc
d = 0
while queue:
r, c, d = queue.popleft()
for nr, nc in neighbors(r, c):
if grid[nr][nc] == 1:
grid[nr][nc] = 2
queue.append((nr, nc, d + 1))
if any(1 in row for row in grid):
return -1
return d（3）课程表
题目
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [a(i), b(i)] ，表示如果要学习课程 a(i) 则 必须 先学习课程 b(i)( )。
例如，先修课程对
[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 。这是不可能的。
提示：
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= a(i), b(i) < numCoursesprerequisites[i]中的所有课程对 互不相同
思考
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# dfs、bfs实现
# bfs实现：
# 时间复杂度: O(n+m)，其中 n 为课程数，m 为先修课程的要求数。这其实就是对图进行广度优先搜索的时间复杂度。
# 空间复杂度: O(n+m)。题目中是以列表形式给出的先修课程关系，为了对图进行广度优先搜索，我们需要存储成邻接表的形式，空间复杂度为 O(n+m)。在广度优先搜索的过程中，我们需要最多 O(n) 的队列空间（迭代）进行广度优先搜索。因此总空间复杂度为 O(n+m)。
edges = collections.defaultdict(list)
indeg = [0] * numCourses
for info in prerequisites:
edges[info[1]].append(info[0])
indeg[info[0]] += 1
q = collections.deque([u for u in range(numCourses) if indeg[u] == 0])
visited = 0
while q:
visited += 1
u = q.popleft()
for v in edges[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return visited == numCourses
（4）实现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
提示：
1 <= word.length, prefix.length <= 2000word和prefix仅由小写英文字母组成insert、search和startsWith调用次数 总计 不超过3 * 10(4)次
思考
class Trie:
def __init__(self):
self.children = [None] * 26
self.isEnd = False
def searchPrefix(self, prefix: str) -> "Trie":
node = self
for ch in prefix:
ch = ord(ch) - ord("a")
if not node.children[ch]:
return None
node = node.children[ch]
return node
def insert(self, word: str) -> None:
node = self
for ch in word:
ch = ord(ch) - ord("a")
if not node.children[ch]:
node.children[ch] = Trie()
node = node.children[ch]
node.isEnd = True
def search(self, word: str) -> bool:
node = self.searchPrefix(word)
return node is not None and node.isEnd
def startsWith(self, prefix: str) -> bool:
return self.searchPrefix(prefix) is not None
# 详细题解：https://leetcode.cn/problems/implement-trie-prefix-tree/solutions/717239/shi-xian-trie-qian-zhui-shu-by-leetcode-ti500/
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)结尾
亲爱的读者朋友：感谢您在繁忙中驻足阅读本期内容！您的到来是对我们最大的支持❤️
正如古语所言："当局者迷，旁观者清"。您独到的见解与客观评价，恰似一盏明灯💡，能帮助我们照亮内容盲区，让未来的创作更加贴近您的需求。
若此文给您带来启发或收获，不妨通过以下方式为彼此搭建一座桥梁： ✨ 点击右上角【点赞】图标，让好内容被更多人看见 ✨ 滑动屏幕【收藏】本篇，便于随时查阅回味 ✨ 在评论区留下您的真知灼见，让我们共同碰撞思维的火花
我始终秉持匠心精神，以键盘为犁铧深耕知识沃土💻，用每一次敲击传递专业价值，不断优化内容呈现形式，力求为您打造沉浸式的阅读盛宴📚。
有任何疑问或建议？评论区就是我们的连心桥！您的每一条留言我都将认真研读，并在24小时内回复解答📝。
愿我们携手同行，在知识的雨林中茁壮成长🌳，共享思想绽放的甘甜果实。下期相遇时，期待看到您智慧的评论与闪亮的点赞身影✨！
万分感谢🙏🙏您的点赞👍👍、收藏⭐🌟、评论💬🗯️、关注❤️💚
自我介绍：一线互联网大厂资深算法研发（工作6年+），4年以上招聘面试官经验（一二面面试官，面试候选人400+），深谙岗位专业知识、技能雷达图，已累计辅导15+求职者顺利入职大中型互联网公司。熟练掌握大模型、NLP、搜索、推荐、数据挖掘算法和优化，提供面试辅导、专业知识入门到进阶辅导等定制化需求等服务，助力您顺利完成学习和求职之旅（有需要者可私信联系）
友友们，自己的知乎账号为“快乐星球”，定期更新技术文章，敬请关注！