二分搜索

1. 寻找左侧边界的二分搜索

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    // 搜索区间为 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    // 检查出界情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

注意 :

  1. left + (right - left) / 2(left + right) / 2的结果相同,但是有效防止了 left 和 right 太大直接相加导致溢出。
  2. 左右边界,mid,取值。

while循环的条件

初始化 right 的赋值是 nums.length - 1,即最后一个元素的索引,而不是 nums.length。

这二者可能出现在不同功能的二分查找中,区别是:前者相当于两端都闭区间 [left, right],这个区间其实就是每次进行搜索的区间。后者相当于左闭右开区间 [left, right),因为索引大小为 nums.length 是越界的。

边界判断

由于 while 的退出条件是 left == right + 1,区间的形式就是 [right + 1, right],所以当 target 比 nums 中所有元素都大时,会存在以下情况使得索引越界,因此,最后返回结果的代码应该检查越界情况

2. 寻找右侧边界的二分查找

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 这里改成收缩左侧边界即可
            left = mid + 1;
        }
    }
    // 这里改为检查 right 越界的情况
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

回溯算法(DFS)

回溯算法其实就是DFS算法,本质上就是一种暴力穷举算法。采用试错的思想,尝试分步的去解决问题。在分步解决问题的过程中,它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。代码框架如下所示:

  1. 路径:也就是已经做出的选择。

  2. 选择列表:也就是你当前可以做的选择。

  3. 结束条件:也就是到达决策树底层,无法再做选择的条件。

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

要在递归之前做出选择,在递归之后撤销刚才的选择,就能正确得到每个节点的选择列表和路径。

BFS算法

把一些问题抽象成图,本质就是在一幅中找到从起点 start 到终点 target 的最近距离,但是空间复杂度高,而 DFS 的空间复杂度较低。

// 计算从起点 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++;
    }
}

cur.adj() 泛指 cur 相邻的节点,比如说二维数组中,cur 上下左右四面的位置就是相邻节点;visited 的主要作用是防止走回头路,大部分时候都是必须的,但是像一般的二叉树结构,没有子节点到父节点的指针,不会走回头路就不需要 visited

动态规划

动态规划问题的一般形式就是求最值,核心问题是穷举。动态规划存在重叠子问题和最优子结构,可以通过dp数组来进行剪枝优化,最后写出状态转移方程。

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值:
    for 状态2 in 状态2的所有取值:
        for ...
            dp[状态1][状态2][...] = 求最值(选择1,选择2...)

贪心算法

贪心算法是动态规划算法的一个特例,相比动态规划,使用贪心算法需要满足更多的条件(贪心选择性质),但是效率比动态规划要高。

贪心选择性质:每一步都做出一个局部最优的选择,最终的结果就是全局最优。

分治算法

分治算法通过将原问题分解成小规模的子问题,然后根据子问题的结果构造出原问题的答案。分治算法也需要满足一些条件,原问题结果应可以通过合并子问题结果来计算。

  1. 不思考整体,而是把目光聚焦局部
  2. 明确递归函数的定义是什么,相信并且利用好函数的定义

Q.E.D.