leetcode-hot100-图论

时间:2024-03-23 20:19:58

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 门课程,记为 0numCourses - 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;
    }
};

总结:拓扑排序问题

  1. 根据依赖关系,构建邻接表、入度数组。
  2. 选取入度为 0 的数据,根据邻接表,减小依赖它的数据的入度。
  3. 找出入度变为 0 的数据,重复第 2 步。
  4. 直至所有数据的入度为 0,得到排序,如果还有数据的入度不为 0,说明图中存在环。