leetcode刷题记录——图

200 岛屿数量 Medium

给你一个由 '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.length

n == grid[i].length

1 <= m, n <= 300

grid[i][j] 的值为 '0' 或 '1'

思路

解决矩阵搜索问题通常直接使用DFS去做。

这道题的通用思路就是对整个矩阵进行遍历，当遇到 grid[i][j] 的时候开始DFS，将周围所有的 1 都置为 0，这样就能找到所有的岛屿。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from typing import List
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid: return 0
        m, n = len(grid), len(grid[0])
        res = 0
        def dfs(i, j):
            if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] == '0':
                return 
            grid[i][j] = '0'
            for x, y in (i+1,j),(i-1,j),(i,j+1),(i,j-1):
                dfs(x, y)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    dfs(i, j)
                    res += 1
        return res

时间复杂度

时间复杂度O(m * n)，空间复杂度O(m * n)，执行时间248ms，消耗内存18.6MB

130 被围绕的区域 Medium

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获 所有 被围绕的区域：

连接：一个单元格与水平或垂直方向上相邻的单元格连接。

区域：连接所有 'O' 的单元格来形成一个区域。

围绕：如果您可以用 'X' 单元格 连接这个区域，并且区域中没有任何单元格位于 board
边缘，则该区域被 'X' 单元格围绕。

通过将输入矩阵 board 中的所有 'O' 替换为 'X' 来 捕获被围绕的区域。

示例 1：

输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

解释：

130.1

在上图中，底部的区域没有被捕获，因为它在 board 的边缘并且不能被围绕。

示例 2：

输入：board = [["X"]]

输出：[["X"]]

提示：

m == board.length

n == board[i].length

1 <= m, n <= 200

board[i][j] 为 'X' 或 'O'

思路

核心思路和前一题一样，都是先对整个矩阵进行遍历，遇到我们符合条件的先将其进行标记。

这里需要注意的是，我们是将周围没有 O 的标记为 ?，而后面将剩余的O全部标记为 X。同时也要注意我们是先标记为 X 后将 ? 还原为 O，不然会导致结果错误。

代码

这里给出两个版本的代码，思路是一样的，一个是我之前写的，一个是我现在写的。

第一版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        if not board:return None
        m, n = len(board), len(board[0])
        def dfs(i, j):
            if i < 0 or j < 0 or i >= m or j >= n or board[i][j] != 'O':
                return 
            board[i][j] = 'B'
            for x, y in (i + 1), (i - 1), (i, j + 1), (i, j - 1):
                dfs(x, y)
        for i in range(m):
            if board[i][0] == 'O':
                dfs(i, 0)
            if board[i][n - 1] == 'O':
                dfs(i, n - 1)
        for j in range(n):
            if board[0][j] == 'O':
                dfs(0, j)
            if board[m - 1][j] == 'O':
                dfs(m - 1, j)
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                if board[i][j] == 'B':
                    board[i][j] = 'O'

第二版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        if not board: return None
        m, n = len(board), len(board[0])
        def dfs(board, i, j):
            if i < 0 or j < 0 or i >= m or j >= n or board[i][j] != 'O':
                return
            board[i][j] = '?'
            dfs(board, i + 1, j)
            dfs(board, i - 1, j)
            dfs(board, i, j + 1)
            dfs(board, i, j - 1)
        for i in range(m):
            for j in range(n):
                if i == 0 or j == 0 or i == m - 1 or j == n - 1:
                    if board[i][j] == 'O':
                        dfs(board, i, j)
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                if board[i][j] == '?':
                    board[i][j] = 'O'

时间复杂度

第一版时间复杂度O(m * n)，空间复杂度O(min(m, n))，执行时间40ms，消耗内存20.3MB
第二版时间复杂度O(m * n)，空间复杂度O(min(m, n))，执行时间54ms，消耗内存20.3MB

133 克隆图 Medium

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

1
2
3
4
class Node {
    public int val;
    public List<Node> neighbors;
}

测试用例格式：

简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

示例 1：

133.1
输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
解释：
图中有 4 个节点。
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

示例 2：

133.2
输入：adjList = [[]]
输出：[[]]
解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。

示例 3：

输入：adjList = []
输出：[]
解释：这个图是空的，它不含任何节点。

提示：

这张图中的节点数在 [0, 100] 之间。

1 <= Node.val <= 100

每个节点值 Node.val 都是唯一的，

图中没有重复的边，也没有自环。

图是连通图，你可以从给定节点访问到所有节点。

思路

简单来说就是使用一个 DFS 去遍历每个节点，然后将每个节点的值都拷贝过来。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
from typing import Optional
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        oldToNew = {None: None}
        def dfs(node):
            if node in oldToNew:
                return oldToNew[node]
            copy = Node(node.val)
            oldToNew[node] = copy
            for nei in node.neighbors:
                copy.neighbors.append(dfs(nei))
            return copy
        return dfs(node) if node else None

时间复杂度

时间复杂度O(V + E)，空间复杂度O(E)，执行时间44ms，消耗内存16.5MB

399 除法求值 Medium

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

注意：未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。

示例 1：

输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
注意：x 是未定义的 => -1.0

示例 2：

输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
输出：[3.75000,0.40000,5.00000,0.20000]
示例 3：

输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出：[0.50000,2.00000,-1.00000,-1.00000]

提示：

1 <= equations.length <= 20

equations[i].length == 2

1 <= Ai.length, Bi.length <= 5

values.length == equations.length

0.0 < values[i] <= 20.0

1 <= queries.length <= 20

queries[i].length == 2

1 <= Cj.length, Dj.length <= 5

Ai, Bi, Cj, Dj 由小写英文字母与数字组成

思路

这题首先需要搞明白两个节点之间我们要怎么去算，按照数学逻辑来看我们已知 a:b b:c，我们相乘就可以得到 a:c。并且要得到自身到自身的值，也就是1.0。同时还需要得到当 x 不在我们输入的 equations 中的情况，所以我们的结果需要用 -1.0 直接填充。

明白了数理逻辑就可以直接开写，这里我们将直接转换为一个有向图，然后用BFS去做。构建图的部分直接看代码，我们重点说一下处理查询的部分。

对于我们的查询我们可以使用 qx and qy 去辅助完成，即找到 qx 到 qy 的路径并计算得到权值，如果找到了就会被添加到ans表中。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        # 图结构构建
        graph = {}
        for (s, e), v in zip(equations, values):
            if s not in graph:
                graph[s] = {} # 存储neighbor的hash
            graph[s][e] = v
            if e not in graph:
                graph[e] = {}
            graph[e][s] = 1 / v
            graph[s][s] = 1.0
            graph[e][e] = 1.0
        queue = [] # BFS的队列
        n = len(queries)
        ans = [-1.0] * n
        
        # 找最短路径
        for i, (qx, qy) in enumerate(queries):
            if qx not in graph or qy not in graph: continue # x不在graph里面就跳过
            queue = [[qx, 1.0]] # start
            visited = set([qx]) # 存储已经处理过的
            while queue:
                node, mul = queue.pop(0)
                # 枚举并处理节点
                for neighbor, weight in graph[node].items():
                    if neighbor == qy:
                        ans[i] = mul * weight
                        break
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append([neighbor, mul * weight])
        return ans

时间复杂度

时间复杂度O(V + E + Q)，空间复杂度O(V + E + Q)，执行时间42ms，消耗内存16.53

其中 V 表示节点数量， E 表示边的数量， Q 表示查询的数量。

207 课程表 Medium

你这个学期必须选修 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 。这是不可能的。

提示：

1 <= numCourses <= 2000

0 <= prerequisites.length <= 5000

prerequisites[i].length == 2

0 <= ai, bi < numCourses

prerequisites[i] 中的所有课程对 互不相同

思路

我们使用一个入度数组和一个邻接表来完成这个题目。

首先完成入度数组和邻接表的遍历。接下来使用拓扑排序去完成排序，借助一个队列。

这里需要注意，我们的入度为0的时候就需要将其加入队列，最终如果没有数了，就表示我们这个图是没有环的，也就是课程表能够完成学习。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 初始化入度数组和邻接表
        in_degree = [0] * numCourses
        adjacency = [[] for _ in range(numCourses)]
        
        # 构建邻接表和入度数组
        for cur, pre in prerequisites:
            adjacency[pre].append(cur)
            in_degree[cur] += 1
        
        # 初始化队列，将所有入度为0的节点加入队列
        queue = deque()
        for i in range(numCourses):
            if in_degree[i] == 0:
                queue.append(i)
        
        # 拓扑排序
        while queue:
            node = queue.popleft()
            numCourses -= 1
            for neighbor in adjacency[node]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
        
        # 如果所有节点都被访问过，说明没有环，可以完成所有课程
        return numCourses == 0

时间复杂度

时间复杂度O(V + E)，空间复杂度O(V + E)，执行时间42ms，消耗内存17.5MB

210 课程表 II Medium

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

示例 3：

输入：numCourses = 1, prerequisites = []
输出：[0]

提示：

1 <= numCourses <= 2000

0 <= prerequisites.length <= numCourses * (numCourses - 1)

prerequisites[i].length == 2

0 <= ai, bi < numCourses

ai != bi

所有[ai, bi] 互不相同

思路

整体上和前一道题几乎一模一样，唯独需要一个 res 来装我们从 queue 里 pop 出来的变量。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        in_degree = [0] * numCourses
        adjacency = [[] for _ in range(numCourses)]
        
        for cur, pre in prerequisites:
            adjacency[pre].append(cur)
            in_degree[cur] += 1
            
        queue = deque()
        for i in range(numCourses):
            if in_degree[i] == 0:
                queue.append(i)
        res = []
        while queue:
            node = queue.popleft()
            res.append(node)
            for neighbor in adjacency[node]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
        return res if len(res) == numCourses else []

时间复杂度

时间复杂度O(V + E)，空间复杂度O(V + E)，执行时间38ms，消耗内存17.6MB

刷题记录
#Leetcode #刷题 #图
leetcode刷题记录——图
https://www.lx02918.ltd/2024/08/22/leetcode-图/
作者
Seth
发布于
2024年8月22日
许可协议