算法模板 | Elaine's Blog

1. 广度优先搜索BFS

数据结构：Queue队列

使用广度优先搜索（ BFS ）的两个主要方案：遍历或找出最短路径，通常发生在树或图中。

在特定问题中执行 BFS 之前确定结点和边缘非常重要。通常，结点将是实际结点或是状态，而边缘将是实际边缘或可能的转换。

1.1 BFS-模板I

int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed
    int step = 0;       // number of steps neeeded from root to current node
    // initialize
    add root to queue;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // iterate the nodes which are already in the queue
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                add next to queue;
            }
            remove the first node from queue;
        }
    }
    return -1;          // there is no path from root to target
}

如代码所示，在每一轮中，队列中的结点是等待处理的结点。在每个更外一层的 while 循环之后，我们距离根结点更远一步。变量 step 指示从根结点到我们正在访问的当前结点的距离

1.2 BFS-模板II

有时，确保我们永远不会访问一个结点两次很重要。否则，我们可能陷入无限循环。

如果是这样，我们可以在上面的代码中添加一个哈希集usedorvisited来解决这个问题。这是修改后的伪代码：

/**
 * Return the length of the shortest path between root and target node.
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed
    Set<Node> used;     // store all the used nodes
    int step = 0;       // number of steps neeeded from root to current node
    // initialize
    add root to queue;
    add root to used;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // iterate the nodes which are already in the queue
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                if (next is not in used) {
                    add next to queue;
                    add next to used;
                }
            }
            remove the first node from queue;
        }
    }
    return -1;          // there is no path from root to target
}

有两种情况你不需要使用哈希集：

你完全确定没有循环，例如，在树遍历中；
你确实希望多次将结点添加到队列中。

2. 深度优先搜索DFS

数据结构：Stack栈

在大多数情况下，我们在能使用 BFS 时也可以使用 DFS。但是有一个重要的区别：遍历顺序。

与 BFS 不同，更早访问的结点可能不是更靠近根结点的结点。因此，你在 DFS 中找到的第一条路径可能不是最短路径。

2.1 DFS-模板I（递归）

/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(Node cur, Node target, Set<Node> visited) {
    return true if cur is target;
    for (next : each neighbor of cur) {
        if (next is not in visited) {
            add next to visted;
            return true if DFS(next, target, visited) == true;
        }
    }
    return false;
}

当我们递归地实现 DFS 时，似乎不需要使用任何栈。但实际上，使用的是由系统提供的隐式栈，也称为调用栈（Call Stack）。

在上面的模板中，我们在找到第一条路径时停止。

如果你想找到最短路径呢？

提示：再添加一个参数来指示你已经找到的最短路径。

2.2 DFS-模板II

递归解决方案的优点是它更容易实现。但是，存在一个很大的缺点：如果递归的深度太高，你将遭受堆栈溢出。在这种情况下，您可能会希望使用 BFS，或使用显式栈实现 DFS。

/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(int root, int target) {
    Set<Node> visited;
    Stack<Node> s;
    add root to s;
    while (s is not empty) {
        Node cur = the top element in s;
        return true if cur is target;
        for (Node next : the neighbors of cur) {
            if (next is not in visited) {
                add next to s;
                add next to visited;
            }
        }
        remove cur from s;
    }
    return false;
}

该逻辑与递归解决方案完全相同。但我们使用 while 循环和栈来模拟递归期间的系统调用栈。

3. 双指针

3.1 情景一

使用双指针的典型场景之一是你想要：

从两端向中间迭代数组。

这时你可以使用双指针技巧：

一个指针从头部开始，而另一个指针从尾部开始。

也就是从用一个指针迭代变成用两个指针迭代

这种技巧经常在排序数组中使用。

一个经典问题：

反转数组中的元素。比如数组为 ['h', 'e', 'l', 'l', 'o']，反转之后变为 ['o', 'l', 'l', 'e', 'h']。

使用双指针技巧，其思想是分别将两个指针分别指向数组的开头及末尾，然后将其指向的元素进行交换，再将指针向中间移动一步，继续交换，直到这两个指针相遇。

3.2 情景二

需要使用双指针技巧的另一种非常常见的情况：

同时有一个慢指针和一个快指针。

两个指针同方向移动，不同速度。

可以用来解决：滑动窗口问题

解决这类问题的关键是:

确定两个指针的移动策略。（有时贪心算法有关）

快指针什么时候移动？慢指针什么时候移动？快慢指针移动步数时候有联系？

与前一个场景类似，你有时可能需要在使用双指针技巧之前对数组进行排序，也可能需要运用贪心法则来决定你的运动策略。

4. 二分查找

二分查找是一种在每次比较之后将查找空间一分为二的算法。每次需要查找集合中的索引或元素时，都应该考虑二分查找。

如果集合是无序的，我们在应用二分查找之前先对其进行排序。

二分查找三部分

二分查找一般由三个主要部分组成：

预处理 —— 如果集合未排序，则进行排序。
二分查找 —— 使用循环或递归在每次比较后将查找空间划分为两半。
后处理 —— 在剩余空间中确定可行的候选者。

4.1 模版I

场景：用于查找可以通过访问数组中的单个索引来确定的元素或条件。

int binarySearch(int[] nums, int target){
  if(nums == null || nums.length == 0)
    return -1;

  int left = 0, right = nums.length - 1;
  while(left <= right){
    // Prevent (left + right) overflow
    // 用减法，防止溢出
    int mid = left + (right - left) / 2;
    if(nums[mid] == target){ return mid; }
    // target 在右区间，所以[middle + 1, right]
    else if(nums[mid] < target) { left = mid + 1; }
    // target 在左区间，所以[left, middle - 1]
    else { right = mid - 1; }
  }

  // End Condition: left > right
  return -1;
}

初始条件：left = 0, right = length-1
终止：left > right
向左查找：right = mid-1
向右查找：left = mid+1

关键属性：

二分查找的最基础和最基本的形式。
查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。
不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。

4.2 模版II

场景：用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。

int binarySearch(int[] nums, int target){
  if(nums == null || nums.length == 0)
    return -1;

  //这边要注意right是数组的长度
  // 定义target在左闭右开的区间里，即：[left, right)
  int left = 0, right = nums.length;
  
  // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
  while(left < right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if(nums[mid] == target){ 
      return mid; 
    }
    //  target 在右区间，在[middle + 1, right)中
    else if(nums[mid] < target) { 
      left = mid + 1; 
    }
    // target 在左区间，在[left, middle)中
    else { 
      right = mid; 
    }
  }

  // Post-processing:
  // End Condition: left == right
  if(left != nums.length && nums[left] == target) return left;
  return -1;
}

初始条件：left = 0, right = length
终止：left == right
向左查找：right = mid
向右查找：left = mid+1

关键属性：

一种实现二分查找的高级方法。
查找条件需要访问元素的直接右邻居。
使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
保证查找空间在每一步中至少有 2 个元素。
需要进行后处理。当你剩下 1 个元素时，循环 / 递归结束。需要评估剩余元素是否符合条件。

4.3 模版III

场景：二分查找的另一种独特形式。用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。

int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0)
        return -1;

  	// 二分查找 --- (left, right)
    int left = 0, right = nums.length - 1;
    while (left + 1 < right){
        // Prevent (left + right) overflow
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
          	//  target 在右区间，在(middle, right)中
            left = mid;
        } else {
          	// target 在左区间，在(left, middle)中
            right = mid;
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if(nums[left] == target) return left;
    if(nums[right] == target) return right;
    return -1;
}

初始条件：left = 0, right = length-1
终止：left + 1 == right
向左查找：right = mid
向右查找：left = mid

关键属性：

实现二分查找的另一种方法。
搜索条件需要访问元素的直接左右邻居。
使用元素的邻居来确定它是向右还是向左。
保证查找空间在每个步骤中至少有 3 个元素。
需要进行后处理。当剩下 2 个元素时，循环 / 递归结束。需要评估其余元素是否符合条件。

4.4 模版分析

三个模版的区别都用红色标记出来，它们的不同之处在于：

左、中、右索引的分配。
循环或递归终止条件。
后处理的必要性。

模板 #1 和 #3 是最常用的，几乎所有二分查找问题都可以用其中之一轻松实现。模板 #2 更高级一些，用于解决某些类型的问题。

模版 #1 `left <= right`

二分查找的最基础和最基本的形式。
查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。
不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。

模版 #2 `left < right`

一种实现二分查找的高级方法。
查找条件需要访问元素的直接右邻居。
使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
保证查找空间在每一步中至少有 2 个元素。
需要进行后处理。当你剩下 1 个元素时，循环 / 递归结束。需要评估剩余元素是否符合条件。

模版 #3 `left + 1 < right`

实现二分查找的另一种方法。
搜索条件需要访问元素的直接左右邻居。
使用元素的邻居来确定它是向右还是向左。
保证查找空间在每个步骤中至少有 3 个元素。
需要进行后处理。当剩下 2 个元素时，循环 / 递归结束。需要评估其余元素是否符合条件。

注：本篇内容主要来自几本力扣的LeetBook (LeetCode)

1. 广度优先搜索BFS

1.1 BFS-模板I

1.2 BFS-模板II

2. 深度优先搜索DFS

2.1 DFS-模板I（递归）

2.2 DFS-模板II

3. 双指针

3.1 情景一

3.2 情景二

4. 二分查找

二分查找三部分

4.1 模版I

4.2 模版II

4.3 模版III

4.4 模版分析

模版 #1 left <= right

模版 #2 left < right

模版 #3 left + 1 < right

模版 #1 `left <= right`

模版 #2 `left < right`

模版 #3 `left + 1 < right`