目录
  1. 1. 前言
  2. 2. BFS
    1. 2.1. 思想
      1. 2.1.1. 单向BFS(终点未知)
      2. 2.1.2. 模板
      3. 2.1.3. 双向BFS(终点已知)
      4. 2.1.4. 模板
  3. 3. 1091-二进制矩阵中的最短路径
    1. 3.1. 题目
    2. 3.2. 题解
  4. 4. 279-完全平方数
    1. 4.1. 题目
    2. 4.2. 题解
  5. 5. 127-单词接龙
    1. 5.1. 题目
    2. 5.2. 题解
  6. 6. DFS
    1. 6.1. 思想
  7. 7. 695-岛屿最大面积
    1. 7.1. 题目
    2. 7.2. 题解
  8. 8. 200-岛屿数量
    1. 8.1. 题目
    2. 8.2. 题解
  9. 9. 547-朋友圈
    1. 9.1. 题目
    2. 9.2. 题解
  10. 10. 130-被围绕的区域
    1. 10.1. 题目
    2. 10.2. 题解
  11. 11. 417-太平洋大西洋水流问题
    1. 11.1. 题目
    2. 11.2. 题解
leetcode-BFS&DFS

前言

回顾BFS和DFS算法后,完成BFS和DFS算法在leetcode的经典题。

  • BFS
    • 1091-二进制矩阵中的最短路径
    • 279-完全平方数
    • 127-单词接龙
  • DFS
    • 695-岛屿的最大面积
    • 200-岛屿数量
    • 547-朋友圈
    • 130-被围绕的区域
    • 417-太平洋大西洋水流问题

BFS

思想

单向BFS(终点未知)

 广度优先搜索就是把一些问题抽象成一个图,然后一层一层进行遍历,每层遍历都是以上一层遍历的结果为起点,遍历一个距离能访问到的所有节点。需要注意的是,遍历过的节点不能再次遍历。

  • 本质就是让你在一幅「图」中找到从起点 start 到终点 target 的最近距离。(图是无权图,无权图是指从一个节点到另一个节点的代价都记为 1。)
  • 我们写 BFS 算法都是用**「队列」**这种数据结构,每次将一个节点周围的所有节点加入队列

 在程序实现BFS时需要考虑以下问题:

  • 队列:用来存储每一轮遍历得到的节点;
  • 标记:对于遍历过的节点,应该将它标记,防止重复遍历。

模板

参考:https://www.cnblogs.com/bham/p/11746312.html

双向BFS(终点已知)

 单向BFS是从起点不断遍历,直到遇到终点。双向BFS则是,从起点和终点不断遍历,直到遇到相交点。和单向BFS不同之处在于,使用的数据结构不再是队列,而是使用哈希表快速判断两个集合是否有想相交点。

模板

def dBFS(graph, start, end):
visited = set()
front = []
back = []
front.append(start)
back.append(end)
while front and back:
nodes = set()
for node in front:
visited.add(node) #加入访问
process(node) # 处理当前node
nodes.append(generate_related_nodes(node)) #获取子节点
front = nodes
# 从较小的set开始
if len(back) < len(front):
front, back = back, front
...
  • 为什么从较小的set开始?
    • 因为按照 BFS 的逻辑,队列(集合)中的元素越多,扩散之后新的队列(集合)中的元素就越多;在双向 BFS 算法中,如果我们每次都选择一个较小的集合进行扩散,那么占用的空间增长速度就会慢一些,效率就会高一些。

1091-二进制矩阵中的最短路径

题目

  • 难度:中等:

  • 题目:在一个 N × N 的方形网格中,每个单元格有两种状态:空(0)或者阻塞(1)。一条从左上角到右下角、长度为 k 的畅通路径,由满足下述条件的单元格 C_1, C_2, ..., C_k 组成:

    • 相邻单元格 C_iC_{i+1} 在八个方向之一上连通(此时,C_iC_{i+1} 不同且共享边或角)
    • C_1 位于 (0, 0)(即,值为 grid[0][0]
    • C_k 位于 (N-1, N-1)(即,值为 grid[N-1][N-1]
    • 如果 C_i 位于 (r, c),则 grid[r][c] 为空(即,grid[r][c] == 0

    返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径,返回 -1 。

  • 示例:

    输入:[[0,1],[1,0]]

    输出:2


    [[0,0,0],[1,1,0],[1,1,0]]

    输出:4
  • 提示:

    • 1 <= grid.length == grid[0].length <= 100
    • grid[i][j]01

题解

  • 从左上角到右下角的最短畅通路径长度,即从左上角到右下角状态为0的最短路径。
#单向BFS
class Solution(object):
def shortestPathBinaryMatrix(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
from collections import deque
n = len(grid)
if n == 1:
return 1
#若起始点或终点堵塞,则不可能有这样的路径
if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
return -1
#注意题目的描述,是返回从 1 到 k 的路径,第一个节点被定为下标 1,
res = 1
path = deque()
#先压入起点
path.append([0, 0])
#BFS模板
while path:
#对BFS的某一层的中所有点向8个方向进行扩展
for _ in range(len(path)):
x, y = path.popleft()
for new_x, new_y in [[x - 1, y - 1], [x - 1, y], [x - 1, y + 1], [x, y - 1],
[x, y + 1], [x + 1, y - 1], [x + 1, y], [x + 1, y + 1]]:
#下面几种continue可以合并一行,这里为看的清楚就分开写了
if new_x == n - 1 and new_y == n - 1:
#如果扩展的点到达了终点
return res + 1
#扩展的点超出边界,则跳过
if not 0 <= new_x < n or not 0 <= new_y < n:
continue
#若扩展的点为阻塞,则跳过
if grid[new_x][new_y] == 1:
continue
#若扩展的点已经访问过,则跳过
if grid[new_x][new_y] == -1:
continue
#若为通畅点
if grid[new_x][new_y] == 0:
#当前层次下已经访问该点
grid[new_x][new_y] = -1
#将扩展的点加入path,到下一层的时候继续扩展
path.append([new_x, new_y])
res += 1 #对某一层的元素都求判定过后,距离加1(同一个层次中的所有点的距离距离起点都是相等的)
return -1
#双向BFS
class Solution(object):
def shortestPathBinaryMatrix(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid or grid[0][0] or grid[-1][-1]:
return -1
n = len(grid)
if n <= 2:
return n
from collections import deque
direcitons = [(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1)]
front,end = set([(0,0)]),set([(n-1,n-1)])
count = 1
while front and end:
if len(front) > len(end):
# 两端走, 哪边的值少走哪边, front也就是当前队列
front,end = end,front
next_queue = set() # 下一个队列
for _ in range(len(front)):
i,j= front.pop()
for dx,dy in direcitons:
x,y = i+dx, j+dy
if (x,y) in end:
#结果坐标在尾队列,结束
return count +1
if 0<=x<n and 0<=y<n and grid[x][y] == 0:
# 已经走过则 赋值为 1, 好马不吃回头草
grid[x][y] = 1
next_queue.add((x,y))
front = next_queue
count += 1

return -1
  • 单向BFS和双向BFS,从大O时间复杂度上看是一样的,只能说双向 BFS 是一种 trick,算法运行的速度会相对快一点。掌握BFS就可以了~
  • 时间复杂度:O(n),因为每个元素遍历了一次,n为元素的个数
  • 空间复杂度:O(k),k为过程中队列的最大元素个数。

279-完全平方数

题目

  • 难度:中等

  • 题目:给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

  • 示例:

    输入: n = 12
    输出: 3
    解释: 12 = 4 + 4 + 4.

    输入: n = 13
    输出: 2
    解释: 13 = 4 + 9.

题解

class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
# 初始化完全平方数列表
square_nums = [i * i for i in range(1, int(n**0.5)+1)]
# 初始化返回结果
count = 0
# 初始化队列遍历保存每一次差值
queue = [n]
#BFS遍历
while queue:
count += 1
next_queue = [] #next_queue = set()
for remainder in queue:
for square_num in square_nums:
if remainder == square_num:
return count
elif remainder < square_num:
break
else:
next_queue.append(remainder - square_num) #next_queue.add(remainder - square_num)
queue = next_queue
return level
  • 注意:在典型的 BFS 算法中,queue 变量通常是数组或列表类型。这里可以使用 set 类型,以消除同一级别中的剩余项的冗余。事实证明,这个小技巧甚至可以增加 5 倍的运行加速。
  • set() 函数创建一个无序不重复元素集,可进行关系测试,删除重复数据,还可以计算交集、差集、并集等。
  • 时间复杂度:O(nh2)O(n^{\frac{h}{2}}),其中 h 是 N 元树的高度。
  • 空间复杂度:O((n)h)O((\sqrt{n})^h),这也是在 h 级可以出现的最大节点数。可以看到,虽然我们保留了一个完全平方数列表,但是空间的主要消耗是队列变量,它跟踪给定 N 元树级别上要访问的剩余节点。

127-单词接龙

题目

  • 难度:中等

  • 题目:给定两个单词(beginWordendWord)和一个字典,找到从 beginWordendWord 的最短转换序列的长度。转换需遵循如下规则:

    • 每次转换只能改变一个字母。
    • 转换过程中的中间单词必须是字典中的单词。
  • 说明:

    • 如果不存在这样的转换序列,返回 0。
    • 所有单词具有相同的长度。
    • 所有单词只由小写字母组成。
    • 字典中不存在重复的单词。
    • 你可以假设 beginWord 和 endWord 是非空的,且二者不相同。
  • 示例:

    输入:
    beginWord = "hit",
    endWord = "cog",
    wordList = ["hot","dot","dog","lot","log","cog"]

    输出: 5

    解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
    返回它的长度 5。


    输入:
    beginWord = "hit"
    endWord = "cog"
    wordList = ["hot","dot","dog","lot","log"]

    输出: 0

    解释: endWord "cog" 不在字典中,所以无法进行转换。

题解

  • Python的defaultdict
    • https://segmentfault.com/a/1190000010081065
    • 这里使用的是collections.defaultdict类。
      • defaultdict是Python内建dict类的一个子类,第一个参数为default_factory属性提供初始值,默认为None。它覆盖一个方法并添加一个可写实例变量。它的其他功能与dict相同,但会为一个不存在的键提供默认值,从而避免KeyError异常。
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
from collections import defaultdict

if endWord not in wordList or not endWord or not beginWord or not wordList:
return 0

L = len(beginWord)

# 以list类名称作为参数,当访问不存在的键,会添加并返回默认值(一个空列表)
all_combo_dict = defaultdict(list)

# 对给定的 wordList 做预处理,找出所有的通用状态。将通用状态记录在字典中,键是通用状态,值是所有具有通用状态的单词。
for word in wordList:
for i in range(L):
all_combo_dict[word[:i] + "*" + word[i+1:]].append(word)

# 将包含 beginWord 和 1 的元组放入队列中,1 代表节点的层次。
# 我们需要返回 endWord 的层次也就是从 beginWord 出发的最短距离。
queue = [(beginWord, 1)]
# 为了防止出现环,使用访问数组记录。
visited = {beginWord: True}

# 当队列中有元素的时候,取出第一个元素,记为 current_word。
while queue:
current_word, level = queue.pop(0)
# 找到current_word所有通用状态,并检查这些通用状态是否存在其它单词的映射,这一步通过检查 all_combo_dict 来实现。
for i in range(L):
intermediate_word = current_word[:i] + "*" + current_word[i+1:]
# 从 all_combo_dict 获得的所有单词,都和 current_word 共有一个通用状态,所以都和 current_word 相连
# 因此将他们加入到队列中。
for word in all_combo_dict[intermediate_word]:
if word == endWord:
return level + 1
if word not in visited:
visited[word] = True
# 对于新获得的所有单词,向队列中加入元素 (word, level + 1) 其中 level 是 current_word 的层次。
queue.append((word, level + 1))
all_combo_dict[intermediate_word] = []
return 0
  • 时间复杂度:O(M×N),其中 M 是单词的长度 ,N 是单词表中单词的总数。找到所有的变换需要对每个单词做 M次操作。同时,最坏情况下广度优先搜索也要访问所有的 N 个单词。
  • 空间复杂度:O(M×N),要在 all_combo_dict 字典中记录每个单词的 M个通用状态。访问数组的大小是 N。广搜队列最坏情况下需要存储 N个单词。

DFS

思想

 深度优先搜索就是把一些问题抽象成一个图,然后一个结点一个结点的遍历,直到没有新的结点可以遍历。

  • 从一个节点出发,使用 DFS 对一个图进行遍历时,能够遍历到的节点都是从初始节点可达的,DFS 常用来求解这种 可达性 问题。
  • BFS 相对 DFS 的最主要的区别是:BFS 找到的路径一定是最短的,但代价就是空间复杂度比 DFS 大很多

 在程序实现 DFS 时需要考虑以下问题:

  • 栈:用栈来保存当前节点信息,当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
  • 标记:和 BFS 一样同样需要对已经遍历过的节点进行标记。

695-岛屿最大面积

题目

  • 难度:中等

  • 题目:给定一个包含了一些 01 的非空二维数组 grid 。一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。

    找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为 0 。)

  • 示例:

    [[0,0,1,0,0,0,0,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,1,1,1,0,0,0],
    [0,1,1,0,1,0,0,0,0,0,0,0,0],
    [0,1,0,0,1,1,0,0,1,0,1,0,0],
    [0,1,0,0,1,1,0,0,1,1,1,0,0],
    [0,0,0,0,0,0,0,0,0,0,1,0,0],
    [0,0,0,0,0,0,0,1,1,1,0,0,0],
    [0,0,0,0,0,0,0,1,1,0,0,0,0]]

    对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ,因为岛屿只能包含水平或垂直的四个方向的 1 。


    [[0,0,0,0,0,0,0,0]]

    对于上面这个给定的矩阵, 返回 0。
  • 注意:给定的矩阵grid 的长度和宽度都不超过 50。

题解

  • 深度优先搜索:遍历网格,在每个网格上,搜索上、下、左、右四个方向的网格的1,连接起来的就是岛屿的面积
  • 需求求解最大面积,因此,不断更新当前岛屿的最大面积
  • 避免重复遍历,将已经搜索过的网格值置为0
class Solution(object):
def maxAreaOfIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
m, n = len(grid), len(grid[0])
def dfs(grid, i, j):
if 0 <= i < m and 0 <= j < n and grid[i][j]:
grid[i][j] = 0
return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j -1)
return 0
result = 0
for x in range(m):
for y in range(n):
result = max(result, dfs(grid, x, y))
return result
  • 时间复杂度:O(m * n),m,n分别是网格行数和列数,每个网格最多遍历一遍
  • 空间复杂度:O(m * n),递归的深度最大可能是整个网格的大小,因此最大可能使用O(m * n)的栈空间

200-岛屿数量

题目

  • 难度:中等

  • 题目:给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外,你可以假设该网格的四条边均被水包围。

  • 示例:

    输入:
    [
    ['1','1','1','1','0'],
    ['1','1','0','1','0'],
    ['1','1','0','0','0'],
    ['0','0','0','0','0']
    ]
    输出: 1


    输入:
    [
    ['1','1','0','0','0'],
    ['1','1','0','0','0'],
    ['0','0','1','0','0'],
    ['0','0','0','1','1']
    ]
    输出: 3
    解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

题解

  • 本题和695题思路是一样的,不一样的地方在于,695题是找上下左右1的最大总数为题目所求,本题是搜索次数为题目所求。
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
def dfs(grid, i ,j):
if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == '1':
grid[i][j] = '0'
dfs(grid, i + 1, j)
dfs(grid, i - 1, j)
dfs(grid, i, j + 1)
dfs(grid, i, j - 1)
return 0

count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
dfs(grid, i, j)
count += 1
return count
  • 时间复杂度:O(m * n),m,n分别是网格行数和列数,每个网格最多遍历一遍
  • 空间复杂度:O(m * n),递归的深度最大可能是整个网格的大小,因此最大可能使用O(m * n)的栈空间

547-朋友圈

题目

  • 难度:中等

  • 题目:班上有 N 名学生。其中有些人是朋友,有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友,B 是 C 的朋友,那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈,是指所有朋友的集合。

    给定一个 N * N 的矩阵 M,表示班级中学生之间的朋友关系。如果M[ i ] [ j ] = 1,表示已知第 i 个和 j 个学生互为朋友关系,否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

  • 示例:

    输入: 
    [[1,1,0],
    [1,1,0],
    [0,0,1]]
    输出: 2
    说明:已知学生0和学生1互为朋友,他们在一个朋友圈。
    第2个学生自己在一个朋友圈。所以返回2。

    输入:
    [[1,1,0],
    [1,1,1],
    [0,1,1]]
    输出: 1
    说明:已知学生0和学生1互为朋友,学生1和学生2互为朋友,所以学生0和学生2也是朋友,所以他们三个在一个朋友圈,返回1。
  • 注意:

    • N 在[1,200]的范围内。
    • 对于所有学生,有M [ i ] [ i ] = 1。
    • 如果有M [ i ] [ j ] = 1,则有M [ j ] [ i ] = 1。

题解

  • 给定的矩阵可以看成图的邻接矩阵。这样我们的问题可以变成无向图连通块的个数。

  • 从每一个结点开始,我们使用一个大小为N的visited的数组(M的大小为N*N),这样visited[i]表示第 i 个元素是否被深度优先搜索访问过。

  • 我们首先选择一个节点,访问任一相邻的节点。然后再访问这一节点的任一相邻节点。这样不断遍历到没有未访问的相邻节点时,回溯到之前的节点进行访问。

  • 连通块就是可以从任意起点到达的所有节点。

  • 因此,连通块的个数,我们从每个未被访问的节点开始深搜,每开始一次搜索就增加 count计数器一次。

  • 扩展:https://leetcode-cn.com/problems/friend-circles/solution/python-shen-du-you-xian-sou-suo-by-alg_bingoxiaodo/

class Solution(object):
def findCircleNum(self, M):
"""
:type M: List[List[int]]
:rtype: int
"""
def dfs(i, visited):
visited[i] = 1
for j in range(len(M)):
if not visited[j] and M[i][j] == 1:
dfs(j, visited)

visited = [0] * len(M)
count = 0
for i in range(len(M)):
if visited[i] == 0:
dfs(i, visited)
count += 1
return count
  • 时间复杂度:O(n^2),整个矩阵都要被遍历,大小为 n^2
  • 空间复杂度:O(n),visited 数组的大小。

130-被围绕的区域

题目

  • 难度:中等

  • 题目:给定一个二维的矩阵,包含 'X''O'字母 O)。找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O''X' 填充。

  • 示例:

    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
  • 解释:

    • 被围绕的区间不会存在于边界上,换句话说,任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上,或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。

题解

  • 先处理边界上的O,把边界上的O先变成B,然后遍历整个二维矩阵,把O变成X,把B变成O。
class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: None Do not return anything, modify board in-place instead.
"""

if not board or not board[0]:
return board

row = len(board)
col = len(board[0])

def dfs(i, j):
board[i][j] = 'B'
for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
tmp_i = i + x
tmp_j = j + y
if 1 <= tmp_i < row and 1 <= tmp_j < col and board[tmp_i][tmp_j] == 'O':
dfs(tmp_i, tmp_j)

for j in range(col):
# 第一行
if board[0][j] == 'O':
dfs(0, j)
# 最后一行
if board[row - 1][j] == 'O':
dfs(row - 1, j)
for i in range(row):
# 第一列
if board[i][0] == 'O':
dfs(i, 0)
# 最后一列
if board[i][col - 1] == 'O':
dfs(i, col - 1)

for i in range(row):
for j in range(col):
# O 变成 X
if board[i][j] == "O":
board[i][j] = "X"
# B 变成 O
if board[i][j] == "B":
board[i][j] = "O"
  • 时间复杂度:O(mn),m和n分别是行数和列数
  • 空间复杂度:O(mn),递归的深度最大可能是整个矩阵的大小,因此最大可能使用O(m * n)的栈空间

417-太平洋大西洋水流问题

题目

  • 难度:中等

  • 题目:给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界,而“大西洋”处于大陆的右边界和下边界。

    规定水流只能按照上、下、左、右四个方向流动,且只能从高到低或者在同等高度上流动。

    请找出那些水流既可以流动到“太平洋”,又能流动到“大西洋”的陆地单元的坐标。

  • 提示:

    • 输出坐标的顺序不重要
    • mn 都小于150
  • 示例:

    给定下面的 5x5 矩阵:

    太平洋 ~ ~ ~ ~ ~
    ~ 1 2 2 3 (5) *
    ~ 3 2 3 (4) (4) *
    ~ 2 4 (5) 3 1 *
    ~ (6) (7) 1 4 5 *
    ~ (5) 1 1 2 4 *
    * * * * * 大西洋

    返回:

    [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).

题解

  • 分别从太平洋和大西洋的边界位置开始遍历,两次遍历的交集,就是所求。
  • 遍历就是按照高度,从高到底,找下一个大于或等于当前的点。
class Solution(object):
def pacificAtlantic(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
if not matrix or not matrix[0]:
return []
# 流向太平洋的位置
res1 = set()
# 流向大西洋的位置
res2 = set()
row = len(matrix)
col = len(matrix[0])

# 从边界遍历
def dfs(i, j, cur, res):
res.add((i, j))
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 matrix[i][j] <= matrix[tmp_i][tmp_j] and (tmp_i, tmp_j) not in res:
dfs(tmp_i, tmp_j, matrix[i][j], res)
# 太平洋
for i in range(row):
dfs(i, 0, 0, res1)
# 太平洋
for j in range(col):
dfs(0, j, 0, res1)
# 大西洋
for i in range(row):
dfs(i, col - 1, 0, res2)
# 大西洋
for j in range(col):
dfs(row - 1, j, 0, res2)

return res1 & res2
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)
文章作者: Lesy
文章链接: https://lesylin.com/2020/07/04/leetcode-BFS-DFS/
文章声明: 转载请注明文章链接
打赏
  • 微信
  • 支付宝

Comment