宽度优先搜索解决了什么问题

广度优先搜索练习题

基于树的BFS

1.1.1.二叉树的层序遍历 (opens new window)

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


class Solution:
  def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
      if not root:
          return []
      ret = list()
      queue = collections.deque([root])
      while queue:
          temp = list()
          for _ in range(len(queue)):
              node = queue.popleft()
              temp.append(node.val)
              if node.left:
                  queue.append(node.left)
              if node.right:
                  queue.append(node.right)
          ret.append(temp)
      return ret

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) [][]int {
  ret := [][]int{}
  if root == nil{
      return ret
  }
  deque := []*TreeNode{root}
  for len(deque) >0 {
      cur_len := len(deque)
      temp_node := make([]*TreeNode, 0)
      tmp := make([]int, 0)
      for j:=0;j<cur_len;j++{
          node := deque[j]
          tmp = append(tmp, node.Val)
          if node.Left != nil{
              temp_node = append(temp_node, node.Left)
          }
          if node.Right != nil{
              temp_node = append(temp_node, node.Right)
          }
      }
      ret = append(ret, tmp)
      deque = temp_node

  }
  return ret
}

// Make sure to add code blocks to your code group

1.1.2.二叉树的锯齿形层序遍历 (opens new window)

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
  def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:

      if not root:
          return []
      queue = collections.deque([root])
      ret = list()
      flag = 1
      while queue:
          temp = list()
          for _ in range(len(queue)):
              node = queue.popleft()
              temp.append(node.val)
              if node.left:
                  queue.append(node.left)
              if node.right:
                  queue.append(node.right)
          if flag == -1:
              temp = temp[::-1]
          flag = -flag
          ret.append(temp)
      return ret

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func zigzagLevelOrder(root *TreeNode) [][]int {
  ret := make([][]int, 0)
  if root == nil{
      return ret
  }
  deque := []*TreeNode{root}
  flag := 1
  for len(deque) >0{
      n := len(deque)
      temp := make([]int, 0)
      for i:=0;i<n;i++{
          node := deque[i]
          temp = append(temp, node.Val)
          if node.Left != nil{
              deque = append(deque, node.Left)
          }
          if node.Right != nil{
              deque = append(deque, node.Right)            }
          }
      
      deque = deque[n:]
      if flag == -1{
          i, j := 0, len(temp)-1
          for i<j{
              temp[i], temp[j] = temp[j], temp[i]
              i++
              j--
          }
      }
      ret = append(ret, temp)
      flag = -flag
      
  }
  return ret

}

// Make sure to add code blocks to your code group

1.1.3.二叉树的序列化与反序列化 (opens new window)

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式 (opens new window)。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例 1：

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

困难题后续补充学习

// Make sure to add code blocks to your code group

基于图的BFS

提示

一般需要set记录访问过的节点

1.2.1.岛屿数量 (opens new window)

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

提示

其实将遍历到为"1"的值变为"0"就是记录访问过的节点

class Solution:
  def numIslands(self, grid: List[List[str]]) -> int:

      def bfs(i, j):
          queue = [(i, j)]
          grid[i][j] = "0"
          while queue:
              x, y = queue.pop(0)
              for a, b in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
                  if a>=0 and a<n and b>=0 and b <m and grid[a][b] == "1":
                      queue.append((a, b))
                      grid[a][b] = "0"

      n, m = len(grid), len(grid[0])
      res = 0
      for i in range(n):
          for j in range(m):
              if grid[i][j] == "1":
                  res += 1
                  bfs(i, j)
      return res

// Make sure to add code blocks to your code group

1.2.2.克隆图 (opens new window)

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

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

class Node {
 public int val;
 public List<Node> neighbors;
}

测试用例格式：

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

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

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

示例 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：

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

示例 3：

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

"""
# Definition for a Node.
class Node:
  def __init__(self, val = 0, neighbors = None):
      self.val = val
      self.neighbors = neighbors if neighbors is not None else []
"""

from typing import Optional
class Solution:
  def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
      
      if not node:
          return node
      
      visited = {}
      # 将给定的第一个节点存贮到哈希表中
      queue = deque([node])
      visited[node] = Node(node.val, [])  # 克隆第一个节点并且保存
      while queue:
          n = queue.popleft()
          for neighbor in n.neighbors:
              if neighbor not in visited:
                  # 如果没有被访问过，就克隆并且存储在哈希表中
                  visited[neighbor] = Node(neighbor.val, [])
                  # 将邻居节点加入队列
                  queue.append(neighbor)
              # 更新当前节点的邻居节点
              visited[n].neighbors.append(visited[neighbor])

      return visited[node]
  

/**
* Definition for a Node.
* type Node struct {
*     Val int
*     Neighbors []*Node
* }
*/

func cloneGraph(node *Node) *Node {
  if node == nil{
      return nil
  }
  visited := make(map[*Node]*Node)
  // 将题目给定的节点添加到队列
  queue := []*Node{node}
  // 克隆第一个节点，并且存贮在hashb表中
  visited[node] = &Node{node.Val, []*Node{}}
  // 广度优先遍历
  for len(queue) > 0{
      n := queue[0]
      queue = queue[1:]
      for _, neighbor := range n.Neighbors{
          if _, ok := visited[neighbor]; !ok{
              // 没有访问过， 就克隆并且存贮在哈希表中
              visited[neighbor] = &Node{neighbor.Val, []*Node{}}
              // 将邻居节点加入队列
              queue = append(queue, neighbor)
          }
          // 更新当前节点的邻居节点
          visited[n].Neighbors = append(visited[n].Neighbors, visited[neighbor])
      }
  }
  return visited[node]
  
}

// Make sure to add code blocks to your code group

1.2.3.单词接龙 (opens new window)

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

• 每一对相邻的单词只差一个字母。
• 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
• sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

困难题后续补充

// Make sure to add code blocks to your code group

1.2.4.被围绕的区域 (opens new window)

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

• **连接：**一个单元格与水平或垂直方向上相邻的单元格连接。
• 区域：连接所有 '0' 的单元格来形成一个区域。
• **围绕：**如果您可以用 '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"]]

解释：

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

示例 2：

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

输出：[["X"]]

class Solution:
  def solve(self, board: List[List[str]]) -> None:
      """
      Do not return anything, modify board in-place instead.
      """
      # 所有区域直接或者间接和边界相连，找到直接或者间接相连的位置做标记
      # dfs 解法
      if len(board) == 1 or len(board[0]) == 1:
          return board
      
      n, m = len(board), len(board[0])
      que = collections.deque()
      for i in range(n):
          if board[i][0] == "O":
              que.append((i, 0))
              board[i][0] = "A"
          if board[i][m - 1] == "O":
              que.append((i, m - 1))
              board[i][m - 1] = "A"
      for i in range(m - 1):
          if board[0][i] == "O":
              que.append((0, i))
              board[0][i] = "A"
          if board[n - 1][i] == "O":
              que.append((n - 1, i))
              board[n - 1][i] = "A"

      while que:
          x, y = que.popleft()
          for mx, my in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
              if 0 <= mx < n and 0 <= my < m and board[mx][my] == "O":
                  que.append((mx, my))
                  board[mx][my] = "A"
      for i in range(n):
          for j in range(m):
              if board[i][j] == "A":
                  board[i][j] = "O"
              elif board[i][j] == "O":
                  board[i][j] = "X"

class Solution:
  def solve(self, board: List[List[str]]) -> None:
      """
      Do not return anything, modify board in-place instead.
      """
      # 所有区域直接或者间接和边界相连，找到直接或者间接相连的位置做标记
      # dfs 解法
      if len(board) == 1 or len(board[0]) == 1:
          return
      def dfs(i, j):
          if not(0<=i<len(board)) or not(0<=j<len(board[0])) or board[i][j] != "O":
              return
          board[i][j] = "A"
          dfs(i+1, j)
          dfs(i-1, j)
          dfs(i, j+1)
          dfs(i, j-1)

      for i in range(len(board[0])):
          dfs(0, i)
          dfs(len(board)-1, i)
      for i in range(len(board)):
          dfs(i, 0)
          dfs(i, len(board[0])-1)
      for i in range(len(board)):
          for j in range(len(board[0])):
              if board[i][j] == "A":
                  board[i][j] = "O"
              elif board[i][j] == "O":
                  board[i][j] = "X"

func solve(board [][]byte)  {

  if len(board) == 1 || len(board[0])== 1{
      return
  }
  
  var dfs func(row, col int)
  dfs = func(row, col int) {
      if !(0<=row && row<len(board)) || !(0<=col && col<len(board[0])) || board[row][col] != 'O'{
          return
      }
      board[row][col] = 'A'
      dfs(row - 1, col)
      dfs(row + 1, col)
      dfs(row, col + 1)
      dfs(row, col - 1)

  }
  for i := range len(board){
      dfs(i, 0)
      dfs(i, len(board)-1)
  }
  for i := range len(board[0]){
      dfs(0, i)
      dfs(len(board)-1, i)
  }
  for i :=  range len(board){
      for j := range len(board[0]){
          if board[i][j] == 'A'{
              board[i][j] = 'O'
          } else if board[i][j] == 'O'{
              board[i][j] = 'X'
          }
      }
  }
}

// Make sure to add code blocks to your code group

1.2.5.打开转盘锁 (opens new window)

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

示例 1:

输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。

示例 2:

输入: deadends = ["8888"], target = "0009"
输出：1
解释：把最后一位反向旋转一次即可 "0000" -> "0009"。

示例 3:

输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：无法旋转到目标数字且不被锁定。

class Solution:
  def openLock(self, deadends: List[str], target: str) -> int:
      if target == "0000":
          return 0

      dead = set(deadends)
      if "0000" in dead:
          return -1
      
      def num_prev(x: str) -> str:
          return "9" if x == "0" else str(int(x) - 1)
      
      def num_succ(x: str) -> str:
          return "0" if x == "9" else str(int(x) + 1)
      
      # 枚举 status 通过一次旋转得到的数字
      def get(status: str) -> Generator[str, None, None]:
          s = list(status)
          for i in range(4):
              num = s[i]
              s[i] = num_prev(num)
              yield "".join(s)
              s[i] = num_succ(num)
              yield "".join(s)
              s[i] = num

      q = deque([("0000", 0)])
      seen = {"0000"}
      while q:
          status, step = q.popleft()
          for next_status in get(status):
              if next_status not in seen and next_status not in dead:
                  if next_status == target:
                      return step + 1
                  q.append((next_status, step + 1))
                  seen.add(next_status)
      
      return -1

func openLock(deadends []string, target string) int {
  const start = "0000"
  if target == start {
      return 0
  }

  dead := map[string]bool{}
  for _, s := range deadends {
      dead[s] = true
  }
  if dead[start] {
      return -1
  }

  // 枚举 status 通过一次旋转得到的数字
  get := func(status string) (ret []string) {
      s := []byte(status)
      for i, b := range s {
          s[i] = b - 1
          if s[i] < '0' {
              s[i] = '9'
          }
          ret = append(ret, string(s))
          s[i] = b + 1
          if s[i] > '9' {
              s[i] = '0'
          }
          ret = append(ret, string(s))
          s[i] = b
      }
      return
  }

  type pair struct {
      status string
      step   int
  }
  q := []pair{{start, 0}}
  seen := map[string]bool{start: true}
  for len(q) > 0 {
      p := q[0]
      q = q[1:]
      for _, nxt := range get(p.status) {
          if !seen[nxt] && !dead[nxt] {
              if nxt == target {
                  return p.step + 1
              }
              seen[nxt] = true
              q = append(q, pair{nxt, p.step + 1})
          }
      }
  }
  return -1
}

// Make sure to add code blocks to your code group

1.2.6.二进制矩阵中的最短路径 (opens new window)

给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

• 路径途经的所有单元格的值都是 0 。
• 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。

畅通路径的长度 是该路径途经的单元格总数。

示例 1：

输入：grid = [[0,1],[1,0]]
输出：2

示例 2：

输入：grid = [[0,0,0],[1,1,0],[1,1,0]]
输出：4

示例 3：

输入：grid = [[1,0,0],[1,1,0],[1,1,0]]
输出：-1

提示

把单元格当成图的节点，如果两个相邻单元格的值都是 0，那么这两个相邻单元格代表的节点之间存在边，且边长为 1。因此问题可以转化为给定一个无权图，求两个节点的最短路径。求无权图的最短路径问题的解法是广度优先搜索。

首先如果 首先如果 grid[0][0]=1 那么显然不存在最短路径，因此返回 -1。使用 dist[x][y] 保存左上角单元格 (0,0) 到某一单元格 (x,y)的最短路径，初始时 dist[0][0] = 1。首先，我们将单元格 (0,0)放入队列中，然后不断执行以下操作：

1. 如果队列为空，那么返回 -1
2. 从队列中取出单元格 (x, y)，如果该单元格等于右下角单元格，那么返回dist[x][y]
3. 遍历该单元格的所有相邻单元格，如果相邻单元格x1, y1 的值为0 且未被访问，那么令dist[x1][y1] = dist[x][y]+1并且将单元格(x1, y1)放入队列中

class Solution:
  def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
      if grid[0][0] == 1:
          return -1
      if len(grid) == 1:
          return len(grid)
      if len(grid[0]) == 1:
          return len(grid[0])

      # 控制方向变量
      n = len(grid)
      directions = [[i, j] for i in [-1, 0 ,1] for j in [-1, 0, 1]]
      directions.remove([0, 0])
      # ist[x][y] 保存左上角单元格 (0,0)(0, 0)(0,0) 到某一单元格 (x,y)(x, y)(x,y) 的最短路径
      dist = [[inf] * n for _ in range(n)] 
      # 初始时 dist[0][0]=1\textit{dist}[0][0] = 1dist[0][0]=1
      dist[0][0] = 1
      que = deque([(0, 0)])
      while que:
          x, y = que.popleft()
          if x == y == n-1:
              return dist[x][y]
          #遍历相邻单元格
          for dx, dy in directions:
              if x+dx <0 or y+dy <0 or x+dx >=n or y+dy >=n: # 越界
                  continue
              if (grid[x+dx][y+dy]) == 1 or dist[x+dx][y+dy] <= dist[x][y]+1: # 单元格值不为 0 或已被访问
                  continue
              dist[x+dx][y+dy] = dist[x][y] + 1
              que.append((x+dx, y+dy))
      return -1

// Make sure to add code blocks to your code group

1.2.7.网格中的最短路径 (opens new window)

给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。

如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1 。

示例 1：

输入： grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
输出：6
解释：
不消除任何障碍的最短路径是 10。
消除位置 (3,2) 处的障碍后，最短路径是 6 。该路径是 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

示例 2：

输入：grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
输出：-1
解释：我们至少需要消除两个障碍才能找到这样的路径。

提示

和上一题很像，只不过每个dist由三元数组组成，不仅记录当前最小路径，还要记录经过了多少障碍物，后续补充

// Make sure to add code blocks to your code group

1.2.8.太平洋大西洋水流问题 (opens new window)

有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。

岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。

示例 1：

输入: heights = [[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]]

示例 2：

输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]

提示

从边出发，只要有比自己高的点，就往高处走，直到走不了为止。 最终返回太平洋和大西洋能走到的点的交集。 说明这些点可以流到太平洋和大西洋。

class Solution:
  def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: 
      # 广度优先遍历
      directions =[(1, 0), (-1, 0), (0, 1), (0, -1)]
      def bfs(queue):
          visited = set(queue)
          while queue:
              x, y = queue.popleft()
              for dx, dy in directions:
                  newx, newy = x + dx, y + dy
                  if (newx, newy) in visited: # 是否访问过
                      continue
                  if newx<0 or newy < 0 or newx >= len(heights) or newy >= len(heights[0])  or heights[newx][newy] < heights[x][y]: # 是否越界  是否可以向四周流动
                      continue
                  visited.add((newx, newy))
                  queue.append((newx, newy))
          return visited
      queue_p = collections.deque()  # 从p 到a
      queue_a = collections.deque()  # 从a 到p
      pacific = set()
      
      for i in range(len(heights)):
          queue_p.append((i, 0))
          queue_a.append((i, len(heights[0])-1 ))

      for j in range(len(heights[0])):
          queue_p.append((0, j))
          queue_a.append((len(heights)-1, j))
      ret = bfs(queue_a) & bfs(queue_p)
      return [list(p) for p in ret]

// Make sure to add code blocks to your code group

拓扑排序

• Leetcode 207 Course Schedule （I, II）
• Leetcode 444 Sequence Reconstruction
• Leetcode 269 Alien Dictionary
• Leetcode 310 Minimum Height Trees
• Leetcode 366 Find Leaves of Binary Tree