廣度優先搜尋&深度優先搜尋

發表於 | 分類於 ，

題目

  • 46 Permutations (Medium)
  • 47 Permutations II (Medium)
  • 51 N-Queens (Hard)
  • 52 N-Queens (Hard)
  • 698 Partition to K Equal Sum Subsets (Medium)
  • 78 Subsets (Medium)
  • 77 Combinations (Medium)
  • 37 Sudoku Solver (Hard)
  • 22 Generate Parentheses (Medium)

islands

  • 200 Number of Islands (Medium)
  • 1254 Number of Closed Islands (Medium)
  • 1020 Number of Enclaves (Medium)
  • 695 Max Area of Island (Medium)
  • 1905 Count Sub Islands (Medium)
  • 694 Number of Distinct Islands (Medium, Premium)

BFS

  • 111 Minimum Depth of Binary Tree (Easy)
  • 752 Open the Lock (Medium)
  • 773 Sliding Puzzle (Hard)
  • 542 01 Matrix (Medium)
  • 994 Rotting Oranges (Medium)

[補充]

  • 112 Path Sum
  • 113 Path Sum II
  • 437 Path Sum III
  • 733 Flood Fill (Easy)

[補充]

  • 1091 Shortest Path in Binary Matrix
  • 797 All Paths From Source to Target

觀念

Backtracking = DFS= 運用遞迴依序窮舉各個維度的數值。暴力法
BFS，BFS 找到的路徑一定是最短的，用空間換取時間。一般來說些奧queue支持

複雜度分析，以求樹的高度、或求最短路徑為例。
DFS 需要O(logN) 空間，時間通常較多
BFS 需要O(N) 空間，時間通常較少

Backtracking 觀念與框架

本質上是DFS 決策樹的遍歷過程。所以算是暴力求解。路徑、當前選擇、結束條件。O(logN)

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private List<TreeNode> traversal(TreeNode root) {     
    List<TreeNode> res = new ArrayList<>(); 
    Stack<TreeNode> stack = new Stack<>(); 
    stack.add(root); 
    while (!stack.empty()) { 
        TreeNode node = stack.peek(); 
        res.add(node);         
        stack.pop();                         
        if (node.right != null) {
           stack.push(node.right);
           }
        if (node.left != null) {
           stack.push(node.left);
           }
     }
     return res;
}

BFS 觀念與框架

找到路徑肯定是最短的，但代價就是空間複雜度比DFS大很多。用queue 輔助。O(N)。用空間換取時間。

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
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路

    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数或是樹的深度

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}