面试常见的四种算法思想,全在这里了

原创
01/15 08:45
阅读数 2.8K

我是架构精进之路,点击上方“关注”,坚持每天为你分享技术干货,私信我回复“01”,送你一份程序员成长进阶大礼包。

 

面试常见的四种算法思想,全在这里了,今天带你一文了解。

1、贪心

贪心算法有很多经典的应用,比如霍夫曼编码(Huffman Coding)、Prim 和 Kruskal 最小生成树算法、还有 Dijkstra 单源最短路径算法。

解决问题步骤

第一步,当我们看到这类问题的时候,首先要联想到贪心算法:针对一组数据,我们定义了限制值和期望值,希望从中选出几个数据,在满足限制值的情况下,期望值最大。
第二步,我们尝试看下这个问题是否可以用贪心算法解决:每次选择当前情况下,在对限制值同等贡献量的情况下,对期望值贡献最大的数据。
第三步,我们举几个例子看下贪心算法产生的结果是否是最优的。

例子1

我们有 m 个糖果和 n 个孩子。我们现在要把糖果分给这些孩子吃,但是糖果少,孩子多(m<n),所以糖果只能分配给一部分孩子。每个糖果的大小不等,这 m 个糖果的大小分别是 s1,s2,s3,……,sm。除此之外,每个孩子对糖果大小的需求也是不一样的,只有糖果的大小大于等于孩子的对糖果大小的需求的时候,孩子才得到满足。假设这 n 个孩子对糖果大小的需求分别是 g1,g2,g3,……,gn。问题是,如何分配糖果,能尽可能满足最多数量的孩子?

我们可以把这个问题抽象成,从 n 个孩子中,抽取一部分孩子分配糖果,让满足的孩子的个数(期望值)是最大的。这个问题的限制值就是糖果个数 m。我们现在来看看如何用贪心算法来解决。对于一个孩子来说,如果小的糖果可以满足,我们就没必要用更大的糖果,这样更大的就可以留给其他对糖果大小需求更大的孩子。另一方面,对糖果大小需求小的孩子更容易被满足,所以,我们可以从需求小的孩子开始分配糖果。因为满足一个需求大的孩子跟满足一个需求小的孩子,对我们期望值的贡献是一样的。

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

例子2

这个问题在我们的日常生活中更加普遍。假设我们有 1 元、2 元、5 元、10 元、20 元、50 元、100 元这些面额的纸币,它们的张数分别是 c1、c2、c5、c10、c20、c50、c100。我们现在要用这些钱来支付 K 元,最少要用多少张纸币呢?

在生活中,我们肯定是先用面值最大的来支付,如果不够,就继续用更小一点面值的,以此类推,最后剩下的用 1 元来补齐。
在贡献相同期望值(纸币数目)的情况下,我们希望多贡献点金额,这样就可以让纸币数更少,这就是一种贪心算法的解决思路。直觉告诉我们,这种处理方法就是最好的。

例子3

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

比如任务调度、教师排课等等问题。
这个问题的解决思路是这样的:我们假设这 n 个区间中最左端点是 lmin,最右端点是 rmax。这个问题就相当于,我们选择几个不相交的区间,从左到右将[lmin, rmax]覆盖上。我们按照起始端点从小到大的顺序对这 n 个区间排序。
我们每次选择的时候,左端点跟前面的已经覆盖的区间不重合的,右端点又尽量小的,这样可以让剩下的未覆盖区间尽可能的大,就可以放置更多的区间。这实际上就是一种贪心的选择方法。

用贪心算法实现霍夫曼编码

假设我有一个包含 1000 个字符的文件,每个字符占 1 个 byte(1byte=8bits),存储这 1000 个字符就一共需要 8000bits,那有没有更加节省空间的存储方式呢?

假设我们通过统计分析发现,这 1000 个字符中只包含 6 种不同字符,假设它们分别是 a、b、c、d、e、f。而 3 个二进制位(bit)就可以表示 8 个不同的字符,所以,为了尽量减少存储空间,每个字符我们用 3 个二进制位来表示。那存储这 1000 个字符只需要 3000bits 就可以了,比原来的存储方式节省了很多空间。不过,还有没有更加节省空间的存储方式呢?

a(000)、b(001)、c(010)、d(011)、e(100)、f(101)

 

霍夫曼编码就要登场了。霍夫曼编码是一种十分有效的编码方法,广泛用于数据压缩中,其压缩率通常在 20%~90% 之间。如何给不同频率的字符选择不同长度的编码呢?根据贪心的思想,我们可以把出现频率比较多的字符,用稍微短一些的编码;出现频率比较少的字符,用稍微长一些的编码。

但是,霍夫曼编码是不等长的,每次应该读取 1 位还是 2 位、3 等等来解压缩呢?这个问题就导致霍夫曼编码解压缩起来比较复杂。为了避免解压缩过程中的歧义,霍夫曼编码要求各个字符的编码之间,不会出现某个编码是另一个编码前缀的情况
假设这 6 个字符出现的频率从高到低依次是 a、b、c、d、e、f。我们把它们编码下面这个样子,任何一个字符的编码都不是另一个的前缀,在解压缩的时候,我们每次会读取尽可能长的可解压的二进制串,所以在解压缩的时候也不会歧义。经过这种编码压缩之后,这 1000 个字符只需要 2100bits 就可以了。

我们把每个字符看作一个节点,并且附带着把频率放到优先级队列中。我们从队列中取出频率最小的两个节点 A、B,然后新建一个节点 C,把频率设置为两个节点的频率之和,并把这个新节点 C 作为节点 A、B 的父节点。最后再把 C 节点放入到优先级队列中。重复这个过程,直到队列中没有数据。

2、分治

分治算法(divide and conquer)的核心思想其实就是四个字,分而治之 ,也就是将原问题划分成 n 个规模较小,并且结构与原问题相似的子问题,递归地解决这些子问题,然后再合并其结果,就得到原问题的解。
分治算法是一种处理问题的思想,递归是一种编程技巧。实际上,分治算法一般都比较适合用递归来实现。分治算法的递归实现中,每一层递归都会涉及这样三个操作:

  • 分解:将原问题分解成一系列子问题;

  • 解决:递归地求解各个子问题,若子问题足够小,则直接求解;

  • 合并:将子问题的结果合并成原问题。

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

  • 原问题与分解成的小问题具有相同的模式;

  • 原问题分解成的子问题可以独立求解,子问题之间没有相关性,这一点是分治算法跟动态规划的明显区别,等我们讲到动态规划的时候,会详细对比这两种算法;

  • 具有分解终止条件,也就是说,当问题足够小时,可以直接求解;

  • 可以将子问题合并成原问题,而这个合并操作的复杂度不能太高,否则就起不到减小算法总体复杂度的效果了。

分治算法应用举例分析

  1. 假设有n个数据,期望数据从小到大排序,那完全有序的数据的有序度就是n(n-1)/2。逆序度等于0;相反,倒序排序的数据的有序度就是0,逆序度是n(n-1)/2。除了这两种极端情况外,我们通过计算有序对或逆序对的个数,来表示数据的有序度或逆序度。

  2. 现在问:如何编程求出数组中的数据有序对个数或逆序对个数?

  3. 最简单的办法:拿每个数字和他后面的数字比较,看有几个比它小。将比它小的数字个数记作k,通过这样的方式,把每个数字都考察一遍后,对每个数字对应的k值求和,最后得到的总和就是逆序对个数。但时间复杂度是O(n^2)。

  4. 用分治算法,套用分治的思想,将书中分成前后两半A1和A2,分别两者中的逆序对数,然后在计算A1和A2之间的逆序对个数k3。那整个数组的逆序对个数就是k1+k2+k3。

  5. 要快速计算出两个子问题A1和A2之间的逆序对个数需要借助归并排序算法。

归并排序算法有个非常关键的操作,即将两个有序的小数组,合并成一个有序的数组。实际上,在合并的过程中,就可以计算这两个小数组的逆序对个数。每次合并操作,都计算逆序对个数,把这些计算出来的逆序对个数求和,就是这个数组的逆序对个数。

求两个数的最大共因子(欧几里得算法)

<?php
/** * 分治算法 * 逻辑: * (1) 找出基线条件,这种条件必须尽可能简单。 * (2) 不断将问题分解(或者说缩小规模),直到符合基线条件 */class dc {    /**     * 最大公因子(欧几里得算法)     * 可以引申到-客厅长宽固定,问选择多大的正方形地砖,可以正好铺满客厅     * @param $a     * @param $b     * @return mixed     */    function greatestCommonFactor($a, $b) {        if ($a < $b) {            $c = $a;            $a = $b;            $b = $c;        }        $c = $a % $b;        if ($c == 0) {            return $b;        } else {            $n = $this->greatestCommonFactor($c, $b);        }        return $n;    }}
dd((new dc())->greatestCommonFactor(160, 56));

分治思想在海量数据处理中的应用

  1. 假设,给10GB的订单文件按照金额排序这样一个需求,看似是一个简单的排序问题,但是因为数据量大,有10GB,而我们的机器的内存可能只有2,3GB这样子,无法一次性加载到内存,也就无法通过单纯地使用快排,归并等基础算法来解决。

  2. 要解决这种数据量大到内装不下的问题,我们就可以利用分治的思想,将海量的数据集合根据某种方法,划分为几个小的数据集合,每个小的数据集合单独加载到内存来解决,然后在将小数据集合合并成大数据集合,实际上利用这种分治的处理思路,不仅能克服内存的限制,还能利用多线程或者多机处理,加快处理的速度。

举例分析

采用分治思想的算法包括:

  1. 快速排序算法

  2. 合并排序算法

  3. 桶排序算法

  4. 基数排序算法

  5. 二分查找算法

  6. 利用递归树求解算法复杂度的思想

  7. 分布式数据库利用分片技术做数据处理

  8. MapReduce模型处理思想

3、回溯

深度优先搜索算法利用的是回溯算法思想。这个算法思想非常简单,但是应用却非常广泛。它除了用来指导像深度优先搜索这种经典的算法设计之外,还可以用在很多实际的软件开发场景中,比如正则表达式匹配、编译原理中的语法分析等。很多经典的数学问题都可以用回溯算法解决,比如数独、八皇后、0-1 背包、图的着色、旅行商问题、全排列等等。
回溯的处理思想,有点类似枚举搜索。我们枚举所有的解,找到满足期望的解。为了有规律地枚举所有可能的解,避免遗漏和重复,我们把问题求解的过程分为多个阶段。每个阶段,我们都会面对一个岔路口,我们先随意选一条路走,当发现这条路走不通的时候(不符合期望的解),就回退到上一个岔路口,另选一种走法继续走。

八皇后问题

<?php
/** * 八皇后问题 * 有一个 8x8 的棋盘,希望往里放 8 个棋子(皇后),每个棋子所在的行、列、对角线都不能有另一个棋子 * Class queen */class queen {    //全局或成员变量,下标表示行,值表示queen存储在哪一列    private $result = [];
    public function cal8queens(int $row) {        // 8个棋子都放置好了,打印结果        if ($row == 8) {            $this->printQueens();            // 8行棋子都放好了,已经没法再往下递归了,所以就return            return;        }
        // 每一行都有8中放法        for ($column = 0; $column < 8; ++$column) {            // 有些放法不满足要求            if ($this->isOk($row, $column)) {                // 第row行的棋子放到了column列                $this->result[$row] = $column;                // 考察下一行                $this->cal8queens($row + 1);            }        }    }
    private function isOk(int $row, int $column) {        $leftUp = $column - 1;        $rightUp = $column + 1;        // 逐行往上考察每一行        for ($i = $row - 1; $i >= 0; --$i) {            // 第i行的column列有棋子吗            if ($this->result[$i] == $column) {                return false;            }            // 考察左上对角线:第i行leftUp列有棋子吗            if ($leftUp >= 0 && $this->result[$i] == $leftUp) {                return false;            }            // 考察右上对角线:第i行rightUp列有棋子吗            if ($rightUp < 8 && $this->result[$i] == $rightUp) {                return false;            }            --$leftUp;            ++$rightUp;        }        return true;    }
    // 打印出一个二维矩阵    private function printQueens() {        for ($row = 0; $row < 8; ++$row) {            for ($column = 0; $column < 8; ++$column) {                echo $this->result[$row] == $column ? "Q " : "* ";            }            echo "\n";        }        echo "\n";    }}
(new Queen())->cal8queens(0);

0-1 背包问题

这个问题的经典解法是动态规划,但是也可以使用回溯算法,实现简单,但是没有那么高效。

0-1 背包问题有很多变体,这里介绍一种比较基础的。有一个背包,背包总的承载重量是 Wkg。现在我们有 n 个物品,每个物品的重量不等,并且不可分割。我们现在期望选择几件物品,装载到背包中。在不超过背包所能装载重量的前提下,如何让背包中物品的总重量最大?
我们可以把物品依次排列,整个问题就分解为了 n 个阶段,每个阶段对应一个物品怎么选择。先对第一个物品进行处理,选择装进去或者不装进去,然后再递归地处理剩下的物品。

<?php
class backpack {    public $maxW;
    // cw表示当前已经装进去的物品的重量和;i表示考察到哪个物品了;    // w背包重量;items表示每个物品的重量;itemCount表示物品个数    // 假设背包可承受重量100,物品个数10,物品重量存储在数组a中,那可以这样调用函数:    // f(0, 0, a, 10, 100)    public function f(int $i, int $cw, array $items, int $itemCount, int $w) {        // cw==w表示装满了;i==n表示已经考察完所有的物品        if ($cw == $w || $i == $itemCount) {            if ($cw > $this->maxW) {                $this->maxW = $cw;            }            return;        }        // 递归调用表示不选择当前物品,直接考虑下一个(第 i+1 个),故 cw 不更新        $this->f($i + 1, $cw, $items, $itemCount, $w);        if ($cw + $items[$i] <= $w) {            // 表示选择了当前物品,故考虑下一个时,cw 通过入参更新为 cw + items[i]            $this->f($i + 1, $cw + $items[$i], $items, $itemCount, $w);        }    }
}

正则表达式

正则表达式中,最重要的就是通配符,通配符结合在一起,可以表达非常丰富的语义。为了方便讲解,我假设正则表达式中只包含“*”和“?”这两种通配符,并且对这两个通配符的语义稍微做些改变,其中,“*”匹配任意多个(大于等于 0 个)任意字符,“?”匹配零个或者一个任意字符。基于以上背景假设,我们看下,如何用回溯算法,判断一个给定的文本,能否跟给定的正则表达式匹配?

我们依次考察正则表达式中的每个字符,当是非通配符时,我们就直接跟文本的字符进行匹配,如果相同,则继续往下处理;如果不同,则回溯。

如果遇到特殊字符的时候,我们就有多种处理方式了,也就是所谓的岔路口,比如“*”有多种匹配方案,可以匹配任意个文本串中的字符,我们就先随意的选择一种匹配方案,然后继续考察剩下的字符。如果中途发现无法继续匹配下去了,我们就回到这个岔路口,重新选择一种匹配方案,然后再继续匹配剩下的字符。

public class Pattern {  private boolean matched = false;  private char[] pattern; // 正则表达式  private int plen; // 正则表达式长度
  public Pattern(char[] pattern, int plen) {    this.pattern = pattern;    this.plen = plen;  }
  public boolean match(char[] text, int tlen) { // 文本串及长度    matched = false;    rmatch(0, 0, text, tlen);    return matched;  }
  private void rmatch(int ti, int pj, char[] text, int tlen) {    if (matched) return; // 如果已经匹配了,就不要继续递归了    if (pj == plen) { // 正则表达式到结尾了      if (ti == tlen) matched = true; // 文本串也到结尾了      return;    }    if (pattern[pj] == '*') { // *匹配任意个字符      for (int k = 0; k <= tlen-ti; ++k) {        rmatch(ti+k, pj+1, text, tlen);      }    } else if (pattern[pj] == '?') { // ?匹配0个或者1个字符      rmatch(ti, pj+1, text, tlen);      rmatch(ti+1, pj+1, text, tlen);    } else if (ti < tlen && pattern[pj] == text[ti]) { // 纯字符匹配才行      rmatch(ti+1, pj+1, text, tlen);    }  }}

回溯算法的思想简单,大部分情况下,都是用来解决广义的搜索问题,也就是,从一组可能的解中,选择出一个满足要求的解。回溯算法非常适合用递归来实现,在实现的过程中,剪枝操作是提高回溯效率的一种技巧。利用剪枝,我们并不需要穷举搜索所有的情况,从而提高搜索效率。

4、动态规划

一个模型三个特征
“一个模型” 指的是动态规划适合解决的问题的模型。把这个模型定义为“多阶段决策最优解模型”。
“三个特征”分别是最优子结构、无后效性和重复子问题。

  1. 最优子结构
    最优子结构指的是,问题的最优解包含子问题的最优解。反过来说就是,我们可以通过子问题的最优解,推导出问题的最优解。如果我们把最优子结构,对应到我们前面定义的动态规划问题模型上,那我们也可以理解为,后面阶段的状态可以通过前面阶段的状态推导出来

  2. 无后效性
    无后效性有两层含义,第一层含义是,在推导后面阶段的状态的时候,我们只关心前面阶段的状态值,不关心这个状态是怎么一步一步推导出来的。第二层含义是,某阶段状态一旦确定,就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型,其实基本上都会满足无后效性。

  3. 重复子问题
    如果用一句话概括一下,那就是,不同的决策序列,到达某个相同的阶段时,可能会产生重复的状态。

解题思路

状态转移表法

回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码
先画出一个状态表。状态表一般都是二维的,所以你可以把它想象成二维数组。其中,每个状态包含三个变量,行、列、数组值。我们根据决策的先后过程,从前往后,根据递推关系,分阶段填充状态表中的每个状态。最后,我们将这个递推填表的过程,翻译成代码,就是动态规划代码了

状态转移方程法

找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码。
状态转移方程法有点类似递归的解题思路。我们需要分析,某个问题如何通过子问题来递归求解,也就是所谓的最优子结构。有两种代码实现方法,一种是递归加“备忘录”,另一种是迭代递推。

min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))

0-1背包问题

我们把整个求解过程分为 n 个阶段,每个阶段会决策一个物品是否放到背包中。每个物品决策(放入或者不放入背包)完之后,背包中的物品的重量会有多种情况,也就是说,会达到多种不同的状态,对应到递归树中,就是有很多不同的节点。

四种算法思想比较分析

那贪心、回溯、动态规划可以归为一类,而分治单独可以作为一类,因为它跟其他三个都不大一样。为什么这么说呢?

前三个算法解决问题的模型,都可以抽象成我们今天讲的那个多阶段决策最优解模型,而分治算法解决的问题尽管大部分也是最优解问题,但是,大部分都不能抽象成多阶段决策模型

回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题,我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况,然后对比得到最优解。不过,回溯算法的时间复杂度非常高,是指数级别的,只能用来解决小规模数据的问题。对于大规模数据的问题,用回溯算法解决的执行效率就很低了。

尽管动态规划比回溯算法高效,但是,并不是所有问题,都可以用动态规划来解决。能用动态规划解决的问题,需要满足三个特征,最优子结构、无后效性和重复子问题。在重复子问题这一点上,动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题,不能有重复子问题,而动态规划正好相反,动态规划之所以高效,就是因为回溯算法实现中存在大量的重复子问题。

贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效,代码实现也更加简洁。不过,它可以解决的问题也更加有限。它能解决的问题需要满足三个条件,最优子结构、无后效性和贪心选择性(这里我们不怎么强调重复子问题)。

其中,最优子结构、无后效性跟动态规划中的无异。“贪心选择性”的意思是,通过局部最优的选择,能产生全局的最优选择。每一个阶段,我们都选择当前看起来最优的决策,所有阶段的决策完成之后,最终由这些局部最优解构成全局最优解。

 

- END -


作者:架构精进之路,专注软件架构研究,技术学习与个人成长,关注并私信我回复“01”,送你一份程序员成长进阶大礼包。


 

往期热文推荐:


「技术架构精进」专注架构研究,技术分享

 

Thanks for reading!

本文分享自微信公众号 - 架构精进之路(jiagou_jingjin)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
1
6 收藏
分享
加载中
更多评论
打赏
0 评论
6 收藏
1
分享
返回顶部
顶部