算法复习

二分搜索是最基础的算法，它解决的问题是：在有序数组里查找某个元素，看它是否存在，存在的话在返回它的位置。

C++ 的 STL 库提供了一个 lower_bound 函数和 upper_bound 函数，用法如下：

lower_bound(vec.begin(), vec.end(), num) 用来查找数组 vec 中第一个大于等于 num 的位置，前提条件是 vec 里的元素是递增的。不存在则返回 vec.end()。

upper_bound(vec.begin(), vec.end(), num) 则是查找数组 vec 中第一个大于 num 的位置。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  vector<int> arr{1, 2, 2, 3, 4, 5, 6};
  int pos1 = lower_bound(arr.begin(), arr.end(), 2) - arr.begin();
  int pos2 = upper_bound(arr.begin(), arr.end(), 2) - arr.begin();
  cout << pos1 << ", " << pos2 << endl;
  return 0;
}

打印出 "1, 3"，也就是 2 的范围是[1, 3) 位置。

另外也可以这样用:

typedef std::pair<int, double> myPair;
std::vector<myPair> vec(5);

lower_bound(vec.begin(), vec.end(), num, 
    [](myPair lhs, myPair rhs) { return lhs.first < rhs.first; })

上面我们用了匿名函数（lambda 表达式），它的用法是:

• [] 不捕获变量
• [=] 按值捕获变量
• [&] 按引用捕获变量
• [&, x] 按值捕获 x，按引用捕获其它变量
• [&x, y] 按引用捕获 x，按值捕获 y

如何自己实现一个 lower_bound 呢？为了通用、简单起见，我们来实现一个 lower_bound(int *arr, int v, int l, int r)，在数组 arr 的[l, r) 位置找第一个大于等于 v 的位置。

int lower_bound(int *arr, int v, int l, int r) {
    while(l < r){
        int m = l + (r - l)/2;
        if(arr[m] < v) { // 中点的数比 v 小，说明答案在中点之后，区间变为[m+1, r)
            l = m + 1;
        } else { // 中点的数大于等于 v，答案就是中点之前包括中点，区间变为[l, m)
            r = m;
        }
    }
    return l; 
}

为什么不是 r=m+1，因为我们永远在找[l, r)里满足条件的，如果 r=m+1，那么m 就有可能被再次计算。

接下来我们实现 upper_bound：

int upper_bound(int *arr, int v, int l, int r) {
    while(l < r){
        int m = l + (r - l)/2;
        if(arr[m] <= v) { // 小于或等于 v，说明答案在中点之后，区间变为[m+1, r)
            l = m + 1;
        } else { // 大于 v，说明答案在中点之后，区间变为[m+1, r)
            r = m;
        }
    }
    return l;
}

于是乎，我们要实现一个二分搜索就可以这样写：

int binary_search(int *arr, int v, int l, int r) {
    int pos = lower_bound(arr, v, l, r);
    if (pos == r) {// 说明[l, r) 内的元素都小于 v
        return -1; 
    }
    if (arr[pos] != v) {// 说明第一个大于等于 v 的数是大于 v 的，后面的数也只会更大
        return -1;
    }
    return pos; // 说明 pos 位置上是 v
}

排序几乎是算法里最常见的需求，里面最著名且最实用的算法有：

• 堆排序
• 快速排序（快排）
• 归并排序
• 基数排序（桶排序）

堆排序

堆其实就是满足每个节点比它的两个孩子节点都小的二叉树，也叫小根堆（当然也有大根堆）。堆排序的思路很简单，将一个无序数组建堆，然后依次取堆顶，并调整。最后就得到了升序的数组了。

虽然堆是二叉树，但是因为它同时是个完全二叉树（只有最后一层的右边可以为空），实现时用一个一维数组就可以完成各种操作。让根节点是 1 会比较好写，每个节点的孩子就是 i<<1, (i<<1) + 1，每个节点的父节点就是 i>>1。

建堆

建堆就是将数组中的元组构建成一个小根堆。我们可以原地建堆或者逐个插入。

原地建堆时，从第 N/2 个开始，从下往上处理到第 1 个，每个进行往下调整：如果比孩子大，则与孩子中比较小的交换，并继续向下调整。

逐个插入则是将数字先追加到小根堆的数组末尾，然后往上调整：如果比父节点小，则与父节点交换，并继续往上调整。

弹出堆顶

虽然建好了堆，但整个数组并不是有序的。每次取堆顶后，需要调整堆，以维护堆的属性。一般可以用最后一个元素替换当前堆顶，然后往下调整。

实现

在代码实现上，其实还有很多 trick。例如：

• 建堆和弹出堆顶后都要做的往下调整操作，可以抽象为一个函数。
• 往下调整中的交换也可以先将这个值存起来，每次用孩子覆盖父节点，孩子的值不更新，直到最后一次把存起来的值放到最后一个拿去更新父节点的孩子的位置上。
• 构建一个大根堆，然后弹出堆顶操作直接把堆顶和最后一个元素交换，最后就在原地得到了升序的数组。

int arr[1000];
void maxHeapify(int fa, int N) {
  int i, s = arr;
  for (i = fa << 1; i <= N; i <<= 1) {
    if (i < N && arr[i] < arr[i + 1]) i++;
    if (s > arr[i]) break;
    arr[i >> 1] = arr[i];
  }
  arr[i >> 1] = s;
}

void buildHeap(int N) {
  for (int i = N / 2; i > 0; i--) {
    maxHeapify(i, N);
  }
}

void heapSort(int N) {
  buildHeap(N);
  for (int i = N; i > 1; i--) {
    int t = arr[i];
    arr[i] = arr[1];
    arr[1] = t;
    maxHeapify(1, i - 1);
  }
}

快速排序

快速排序的思想就是，每次选一个数，通过一系列操作让比这个数小的都在它左边，比它大的都在它右边，但是两边各自是无序的，然后递归处理两边。

这“一系列操作”就是挖出某个位置的值，然后在它右边从左往右找一个比它小的挖出来，填到它的位置，再在左边从右往左找个比它大的，填到右边刚刚挖的那个空，直到两边相遇。

int arr[1000];
void quickSort(int l, int r) {
  if (l >= r) return;
  int num = arr[l];
  int i = l, j = r;
  while (i < j) {
    while (j > i && arr[j] >= num) j--;
    arr[i] = arr[j];

    while (i < j && arr[i] <= num) i++;
    arr[j] = arr[i];
  }
  arr[i] = num;

  quickSort(l, i - 1);
  quickSort(i + 1, r);
}

归并排序

介绍归并排序经常会举这个例子：将两列各自按身高排好的同学，合并成有序的一列。先两两合并，然后 4 个 4 个合并，直到全部人合并为一列。

int arr[1000];

void mergeSort(int l, int r) {
  if (l >= r) return;
  int m = l + r >> 1;
  mergeSort(l, m);
  mergeSort(m + 1, r);

  int tmp[1000];
  int i = l, j = m + 1, k = 0;
  while (i <= m || j <= r) {
    while (i <= m && (j > r || arr[i] <= arr[j])) tmp[k++] = arr[i++];
    while (j <= r && (i > m || arr[j] <= arr[i])) tmp[k++] = arr[j++];
  }

  for (int i = 0; i < k; i++) {
    arr[l + i] = tmp[i];
  }
}

基数排序

基数排序主要是用来解决类似这样的问题：有 1 亿个人，要按年龄排序。

我们直接记录好每个年龄有多少人，然后从小到大的年龄输出人数个该年龄，即可。代码略。

动态规划就是找出问题的状态表达和状态转移方程来解决问题的方法。

最大子串和

1. 求数组中最大的连续子序列（子串）的和。只需要累加前缀和，如果当前是负数就放弃前面的所有数，从新位置继续累加即可。\(dp[i] = max(dp[i – 1] + a[i], a[i])\)

2. 求数组中最大的两段不交叉的连续子序列的和。只需要在每次放弃前面的数时，记录过去得到的最大值，和当前序列的和相加，来更新答案即可。\(ans = max(max(dp[start[i-1]-1] + dp[i – 1] + a[i], dp[i-1] + a[i]))\), 如果前者大(继续当前子序列)：\(start[i] = start[i-1]\), 否则(放弃前面的数) \(start[i] = i\)。更简单的方法是分别从左边和右边求一遍最大连续子序列，然后遍历一遍 max(left[i]+right[i])

最长不下降序列

1. 求数组中最长的不下降序列的长度。只需要维护每个长度最小的结尾值，然后对于当前值，就可以二分找出它可以跟在最长多长序列的后面。同时更新出现过的最大长度。

   dp[L+1] = min(dp[L+1], a[i]) (L=upper_bound(dp, dp+len+1, a[i]) - 1)

注意 dp 初始化为无穷大，dp[0]为 0。

2. 求数组最多可分为多少个不上升子序列。由 Dilworth 定理，对于一个偏序集，其最少反链划分数等于其最长链的长度。因此只要计算出 最长的上升序列 的长度即可

dp[L+1] = min(dp[L+1], a[i]) (L=lower_bound(dp, dp+len+1, a[i]) - 1)

如果是计算最长的下降序列，则需要维护每个长度最大的结尾值

dp[L+1] = max(dp[L+1], a[i]) (L=lower_bound(dp, dp+len+1, a[i]) - 1)

长度不超过 m 的最大连续子序列

暴力解法：遍历起点和终点计算区间和 max{sum[i]-sum[j]}(i=1..n, j=max(0, i-m)..i)。时间复杂度是 \(O(n^2)\)

其实对于每个终点，需要找前 m 个前缀和中的最小值。

这其实就是个 RMQ(Range Minimum/Maximum Query) 问题，可通过某个数据结构可以快速查询区间最小值，这样的数据结构我们知道有 ST 表和线段树。时间复杂度是 \(O(n \log n)\)

不过在这个问题里，注意到两个起点之间，如果某个比另一个的前缀和更大，而且位置更前，那么在它们两中选择后者，答案总是会更优。因此我们可以用单调队列来优化到时间复杂度是 \(O(n)\)。

其实这是一种常见的 DP 优化方法：

转移方程 \(\displaystyle f(i)=\min_{j=b[i]}^{i-1}\{g(j)\} + w(i)\) 满足 \(b[i]\) 随 i 递增，若后面的一个决策更优，那么前面的决策就可以删掉。就可以用单调队列维护决策表。

维护一个单调队列，每次考虑把当前的前缀和加入队列时，就要将之前比它大的前缀和从队列尾一个个丢弃掉，因为它们永远不可能成为某个终点找的最小起点了。并且需要丢弃掉队列头和当前位置距离超过 m 的前缀和。这样我们只要遍历终点，当前队列头就是最小起点。由于每个元素最多进入队列一次，时间复杂度就是 O(n)的了。

另外用堆其实也可以实现，相当于每次把当前的插入堆，并不断把距离超过m 的当前堆顶元素弹出堆。虽然堆里面可能有距离超过 m 的元素，但是在用的时候，一定是拿满足距离不超过 m 的最小值。其实此时的堆的作用和单调队列一样。

#include <deque>

deque<int> q;// 记录下标

for(int i = 0; i<n; i++) {
    if(!q.empty() && q.front() < i - m) {
        p.pop_front();
    }
    ans = max(ans, sum[i] - sum[q.front()]);
    while(!q.empty() && sum[q.back()] >= sum[i]) {
        p.pop_back();
    }
}

滑动窗口最大值

leetcode239

这题和上题类似，上题是找最小的 sum[i] ，这里则是找最大的 a[i]。

和大于 k 的最短连续子序列

考虑暴力：遍历满足 sum[i]-sum[j] > k 的终点和起点

其实就是在为每个终点 i 找一个前缀和小于 sum[i]-k 的最近的起点。

这里我们也可以发现一个性质：在两个起点之间，如果一个比另一个的前缀和大，并且位置更靠前，那么在它们两中选择后者，答案总是会更优。

因此也可以用单调队列。

for(int i = 0; i<n; i++) {
    if(!q.empty() && sum[q.back()]  i - m) {
        p.pop_front();
    }
    ans = max(ans, sum[i] - sum[q.front()]);
    while(!q.empty() && sum[q.back()] >= sum[i]) {
        p.pop_back();
    }
}

不同的子序列

Leetcode 115

给你两个字符串，在S中找出有多少个子序列等于T。

考虑\(dp[i][j]\) 表示 S 的前 j 个字符包含多少个子序列等于 T 的前 i 个字符。那么\(dp[i][j] = dp[i][j-1] + I(S[j]==T[i])\dot dp[i-1][j-1]\)。注意dp[0][i] 要初始化为1。

func numDistinct(s string, t string) int {
    ls := len(s)
    lt := len(t)
    dp := make([][]int, lt+1)
    for i := 0; i <= lt; i++ {
        dp[i] = make([]int, ls+1)
    }
    for i := 0; i <= ls; i++ {
        dp[0][i] = 1
    }
    for i := 1; i <= lt; i++ {
        for j := i; j <= ls; j++ {
            dp[i][j] = dp[i][j-1]
            if t[i-1] == s[j-1] {
                dp[i][j] += dp[i-1][j-1]
            }
        }
    }
    return dp[lt][ls]
}

cuckoo hashing