算法思路
Source
Edit
History

undefined

一、贪心

贪心算法解决问题的步骤

  1. 针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。
  2. 每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。
  3. 举几个例子看下贪心算法产生的结果是否是最优的。

贪心算法主要的缺陷是只在当前的范围内考虑最优解。因此对于那种“前面的选择，会影响后面的选择” 的情况就会出现问题

问题

  1. 分糖果：我们有 m 个糖果和 n 个孩子。糖果少，孩子多（m<n），每个糖果的大小不等，这 m 个糖果的大小分别是 s1，s2，s3，……，sm。除此之外，每个孩子对糖果大小的需求也是不一样的，只有糖果的大小大于等于孩子的对糖果大小的需求的时候，孩子才得到满足。假设这 n 个孩子对糖果大小的需求分别是 g1，g2，g3，……，gn。如何分配糖果，能尽可能满足最多数量的孩子？

    我们每次从剩下的孩子中，找出对糖果大小需求最小的，然后发给他剩下的糖果中能满足他的最小的糖果，这样得到的分配方案，也就是满足的孩子个数最多的方案。

  2. 钱币找零：假设我们有 1 元、2 元、5 元、10 元、20 元、50 元、100 元这些面额的纸币，它们的张数分别是 c1、c2、c5、c10、c20、c50、c100。我们现在要用这些钱来支付 K 元，最少要用多少张纸币呢？

    在贡献相同期望值（纸币数目）的情况下，我们希望多贡献点金额，这样就可以让纸币数更少，

    找零问题不能用贪婪算法，即使有面值为一元的币值也不行：考虑币值为100，99和1的币种，每种各一百张，找396元。 动态规划可求出四张99元，但贪心算法解出需三张一百和96张一元。

  3. 区间覆盖：假设我们有 n 个区间，区间的起始端点和结束端点分别是[l1, r1]，[l2, r2]，[l3, r3]，……，[ln, rn]。我们从这 n 个区间中选出一部分区间，这部分区间满足两两不相交（端点相交的情况不算相交），最多能选出多少个区间呢？

    我们假设这 n 个区间中最左端点是 lmin，最右端点是 rmax。这个问题就相当于，我们选择几个不相交的区间，从左到右将[lmin, rmax]覆盖上。我们按照起始端点从小到大的顺序对这 n 个区间排序。

    我们每次选择的时候，左端点跟前面的已经覆盖的区间不重合的，右端点又尽量小的，这样可以让剩下的未覆盖区间尽可能的大，就可以放置更多的区间。这实际上就是一种贪心的选择方法。

霍夫曼编码

二、分治

分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

分治算法是一种处理问题的思想，递归是一种编程技巧。实际上，分治算法一般都比较适合用递归来实现。分治算法的递归实现中，每一层递归都会涉及这样三个操作：

  1. 分解：将原问题分解成一系列子问题；
  2. 解决：递归地求解各个子问题，若子问题足够小，则直接求解；
  3. 合并：将子问题的结果合并成原问题。

分治算法能解决的问题，一般需要满足下面这几个条件：

  • 原问题与分解成的小问题具有相同的模式；
  • 原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别，等我们讲到动态规划的时候，会详细对比这两种算法；
  • 具有分解终止条件，也就是说，当问题足够小时，可以直接求解；
  • 可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。

问题1: 如何编程求出一组数据的有序对个数或者逆序对个数呢？

比如：[ 2 4 3 1 5 6 ] 这一组数据有4组逆序对： (2, 1) (4, 3) (4, 1) (3, 1)

我们套用分治的思想来求数组 A 的逆序对个数。我们可以将数组分成前后两半 A1 和 A2，分别计算 A1 和 A2 的逆序对个数 K1 和 K2，然后再计算 A1 与 A2 之间的逆序对个数 K3。那数组 A 的逆序对个数就等于 K1+K2+K3。其实就是归并排序的思路

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
29
30
31
32
33
34
35
36
37
38

private int num = 0; // 全局变量或者成员变量

public int count(int[] a, int n) {
  num = 0;
  mergeSortCounting(a, 0, n-1);
  return num;
}

private void mergeSortCounting(int[] a, int p, int r) {
  if (p >= r) return;
  int q = (p+r)/2;
  mergeSortCounting(a, p, q);
  mergeSortCounting(a, q+1, r);
  merge(a, p, q, r);
}

private void merge(int[] a, int p, int q, int r) {
  int i = p, j = q+1, k = 0;
  int[] tmp = new int[r-p+1];
  while (i<=q && j<=r) {
    if (a[i] <= a[j]) {
      tmp[k++] = a[i++];
    } else {
      num += (q-i+1); // 统计p-q之间，比a[j]大的元素个数
      tmp[k++] = a[j++];
    }
  }
  while (i <= q) { // 处理剩下的
    tmp[k++] = a[i++];
  }
  while (j <= r) { // 处理剩下的
    tmp[k++] = a[j++];
  }
  for (i = 0; i <= r-p; ++i) { // 从tmp拷贝回a
    a[p+i] = tmp[i];
  }
}

其他问题

  • 二维平面上有 n 个点，如何快速计算出两个距离最近的点对？
  • 有两个 nn 的矩阵 A，B，如何快速求解两个矩阵的乘积 C=AB？

三、回溯

  • 应用1：八皇后问题
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
std::vector<int> chessboard(8, -1);

void print() {
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if (chessboard[i] == j) {
                std::cout << "Q " << " ";
            } else {
                std::cout << "* " << " ";
            }
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

bool isOk(int row, int line) {
    // 需要检查当前行，当前列，以及撇和捺 都没有
    int leftUp = line-1, rightUp = line+1;
    for (int i = row-1; i >= 0; i--) {
        if (chessboard[i] == line) return false;
        if (leftUp >= 0) {
            if (chessboard[i] == leftUp) return false;
        }
        if (rightUp < 8) {
            if (chessboard[i] == rightUp) return false;
        }
        --leftUp;
        ++rightUp;
    }
    return true;
}

void cal8queens(int row) {
    if (row == 8) {
        print();
        return;
    }
    for (int line = 0; line < 8; line++) {
        if (isOk(row, line)) {
            chessboard[row] = line;
            cal8queens(row+1);
        }
    }
}
  • 应用2：0-1 背包问题：我们有一个背包，背包总的承载重量是 Wkg。现在我们有 n 个物品，每个物品的重量不等，并且不可分割。我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？

对于每个物品来说，都有两种选择，装进背包或者不装进背包。对于 n 个物品来说，总的装法就有 2^n 种，去掉总重量超过 Wkg 的，从剩下的装法中选择总重量最接近 Wkg 的。

还用到搜索剪枝的技巧，就是当发现已经选择的物品的重量超过 Wkg 之后，我们就停止继续探测剩下的物品。

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
29
30
31
32
33
34
35
36
37
class Knapsack {
private:
    int w = 9; // 最大承载重量
    int n = 5; // 物品个数
    std::vector<int> weight = {2,2,4,6,3}; // 每个物品的重量
    // 更进一步优化，因为有求解重复，所以对于重复的求解，可以忽略
    std::vector<std::vector<bool>> mem = std::vector<std::vector<bool>>(5, std::vector<bool>(10, false));

public:
    int result = 0;

public:
    void f(int i, int wc) {
        // 如果 i==n 说明已经遍历完了，应该退出
        // 如果 wc==w 说明当前的重量已经等于最大承载重量了，应该退出。
        // 有情况是直接跳过了最大承载重量，不要紧，有分支也就是后续全部不装入背包
        if (i == n || wc == w) {
            // 需要更新当前重量
            if (wc > result) {
                result = wc;
            }
            return;
        }
        // 如果当前遍历到第 i 个物品，且此时的承载重量为 wc，这个分支已经做过了就剪枝
        if (mem[i][wc]) return;
        // 当前第 i 个物品，此时重量为 wc，这个分支准备遍历；则先标记为 true。
        mem[i][wc] = true;
        // 当前物品不装入背包，进行下一个
        f(i+1, wc);
        // 进行剪枝，如果当前物品装入背包小于等于最大承载重量才装入
        if (wc + weight[i] <= w) {
            // 当前物品装入背包，进行下一个
            f(i + 1, wc + weight[i]);
        }

    }
};

  • 应用3：正则表达式。假设正则表达式中只包含 “*” 和 “?” 这两种通配符，并且对这两个通配符的语义稍微做些改变，其中，“*” 匹配任意多个（大于等于 0 个）任意字符，“?” 匹配零个或者一个任意字符。基于以上背景假设，我们看下，如何用回溯算法，判断一个给定的文本，能否跟给定的正则表达式匹配？

    我们依次考察正则表达式中的每个字符，当是非通配符时，我们就直接跟文本的字符进行匹配，如果相同，则继续往下处理；如果不同，则回溯。如果遇到特殊字符的时候，我们就有多种处理方式了，也就是所谓的岔路口，比如“*” 有多种匹配方案，可以匹配任意个文本串中的字符，我们就先随意的选择一种匹配方案，然后继续考察剩下的字符。如果中途发现无法继续匹配下去了，我们就回到这个岔路口，重新选择一种匹配方案，然后再继续匹配剩下的字符。

    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
    29
    30
    31
    32
    33
    34
    35
    36
    class Pattern {
    private:
        bool matched = false;
        std::string pattern;
        int pLen;
    public:
        explicit Pattern(const std::string& pattern) : pattern(pattern), pLen(pattern.size()) {}

        bool match(const std::string& text) {
            rematch(0, 0, text, text.size());
            return matched;
        }

        void rematch(int ti, int pi, const std::string& text, int tLen) {
            if (matched) return;
            if (pi == pLen) {
                if (ti == tLen) matched = true;
                return;
            }
            if (pattern[pi] == '*') {
                // * 匹配符
                for (int k = 0; k < tLen-ti; k++) {
                    rematch(ti+k, pi+1, text, tLen);
                }
            } else if(pattern[pi] == '?') {
                // ？ 匹配符
                rematch(ti, pi+1, text, tLen);
                rematch(ti+1, pi+1, text, tLen);
            } else {
                // 直接匹配
                if (ti < tLen && text[ti] == pattern[pi]) {
                    rematch(ti+1, pi+1, text, tLen);
                }
            }
        }
    };