200. 岛屿数量
给你一个由 '1'
(陆地)和 '0'
(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
**输入:grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
输出:1
循环遍历所有可能的情况;判断当前位置是否陆地,是 nums++,同时将所有相邻位置置为-1(深度优先遍历);否,继续
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(grid, i, j):
if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
return
grid[i][j] = '-1'
dfs(grid, i - 1, j)
dfs(grid, i + 1, j)
dfs(grid, i, j - 1)
dfs(grid, i, j + 1)
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
count += 1
dfs(grid, i, j)
return count
994. 腐烂的橘子
在给定的 m x n
网格 grid
中,每个单元格可以有以下三个值之一:
- 值
0
代表空单元格; - 值
1
代表新鲜橘子; - 值
2
代表腐烂的橘子。
每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1
。
**输入:grid = [[2,1,1],[1,1,0],[0,1,1]]
输出:4
循环遍历,以2为起始位置,开始广度优先遍历,同时将相邻的1元素置为-2,同时包含一个时间变量,随着深度增加而增加;最后根据是否还有1确定新鲜橘子都被腐烂。
BFS伪代码
while queue 非空:
node = queue.pop()
for node的所有相邻接点 m:
if m 没有访问过:
queue.push(m)
- 将所有腐烂的橘子放入队列
- 进行BFS,找到当前元素所有的相邻元素,如果是新鲜橘子,变成腐烂
- 根据新鲜橘子的个数判断是否全部腐烂
- 因为要记录时间,也就是层数,因此在每次bfs时,先记录本层节点数量
def orangesRotting(self, grid: List[List[int]]) -> int:
M = len(grid)
N = len(grid[0])
queue = []
count = 0 # count 表示新鲜橘子的数量
for r in range(M):
for c in range(N):
if grid[r][c] == 1:
count += 1
elif grid[r][c] == 2:
queue.append((r, c))
round = 0 # round 表示腐烂的轮数,或者分钟数
while count > 0 and len(queue) > 0:
round += 1
n = len(queue)
for i in range(n):
r, c = queue.pop(0)
if r-1 >= 0 and grid[r-1][c] == 1:
grid[r-1][c] = 2
count -= 1
queue.append((r-1, c))
if r+1 < M and grid[r+1][c] == 1:
grid[r+1][c] = 2
count -= 1
queue.append((r+1, c))
if c-1 >= 0 and grid[r][c-1] == 1:
grid[r][c-1] = 2
count -= 1
queue.append((r, c-1))
if c+1 < N and grid[r][c+1] == 1:
grid[r][c+1] = 2
count -= 1
queue.append((r, c+1))
if count > 0:
return -1
else:
return round
207. 课程表
你这个学期必须选修 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 。这是可能的。
类拓扑排序,记录每个节点的入度、出度,先遍历入度为0的节点,同时其指向的节点的入度减1;依次遍历,最后判断是否仍然有入度不为0的元素。
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> inDegree(numCourses); // 入度
unordered_map<int, vector<int>> map; // 指向关系
for (int i = 0; i < prerequisites.size(); ++i) {
inDegree[prerequisites[i][0]]++;
map[prerequisites[i][1]].push_back(prerequisites[i][0]);
}
queue<int> que; // 入度为0,初始节点
for (int i = 0; i < numCourses; ++i) {
if (inDegree[i] == 0) {
que.push(i);
}
}
int count = 0; // 入度可以为0的节点
while (!que.empty()) {
int cur = que.front();
que.pop();
count++;
for (int i = 0; i < map[cur].size(); ++i) {
if (inDegree[map[cur][i]] > 0) {
inDegree[map[cur][i]]--;
if (inDegree[map[cur][i]] == 0) {
que.push(map[cur][i]);
}
}
}
}
return count == numCourses;
}
};
总结:拓扑排序问题
- 根据依赖关系,构建邻接表、入度数组。
- 选取入度为 0 的数据,根据邻接表,减小依赖它的数据的入度。
- 找出入度变为 0 的数据,重复第 2 步。
- 直至所有数据的入度为 0,得到排序,如果还有数据的入度不为 0,说明图中存在环。