做题家：不可不会的“算法设计与分析”！【面试笔试】

最近由于要做测评，遂整理算法设计与分析这一块的内容，复习的同时，与大家分享交流~

喂！算法！逃不掉的！All Right?

分治法

比较典型的有：排序算法（归并排序、快速排序）、傅立叶变换（快速傅立叶变换）等；

其中最重要最常考的是快排，应该都很熟悉了，快速过一遍：

1. 选择一个元素作为"基准"（pivot）。
2. 于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
3. 准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
};

其次，我们需了解下傅立叶变换的基本概念：即它能将满足一定条件的某个函数表示成三角函数（正弦和/或余弦函数）或者它们的积分的线性组合。

• 李永乐老师视频讲解传送门

• 傅里叶变换有哪些具体的应用？（OS：太强了！）

动态规划法

动态规划太重要了！动态规划于算法，可能相对于杜兰特于篮网吧~ ORZ

其中最著名的有背包问题、爬梯子问题（斐波那契数列）、寻找最长公共子串 这三个（每个都是重点常考！）。

• 背包问题

背包问题的基础是【0-1背包问题】，先吃透它：

题目：有 N 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i]，价值是 v[i]。求解将哪些物品装入背包可使价值总和最大。

解：：每种物品仅有一件，可以选择放或不放。用 子问题定义状态：即 f[i][w] 表示前 i 件物品恰放入一个容量为 c 的背包可以获得的最大价值。则其状态转移方程便是：

f[i][c] = max{f[i-1][c], f[i-1][c-w[i]]+v[i]} 

这个方程的释义，即分别对应两种情况：

1. 如果背包不放第 i 件物品，那么问题就转化为 前 i-1 件物品放入容量为 v 的背包中，价值为 f[i-1][c]；

2. 如果放第i件物品，那么问题就转化为 前 i-1 件物品放入剩下的容量为 c-w[i] 的背包中，此时能获得的最大价值就是 f[i-1][c-w[i]]再加上通过放入第 i 件物品获得的价值 v[i]，即f[i-1][c-w[i]]+v[i]。

这两者的最大值就是我们最终的解！

 function knapsack(weights, values, W){
    var n = weights.length -1
    var f = [[]]
    for(var j = 0; j <= W; j++){
        // 边界情况
        if(j < weights[0]){
           f[0][j] = 0
        }else{
           f[0][j] = values[0]
        }
    }
    for(var j = 0; j <= W; j++){
        for(var i = 1; i <= n; i++ ){
            if(!f[i]){ //创建新一行
                f[i] = []
            }
            if(j < weights[i]){ //等于之前的最优值
                f[i][j] = f[i-1][j]
            }else{
                f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]) 
            }
        }
    }
    return f[n][W]
}
var a = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(a)

进一步，自行了解 完全背包问题 。

• 爬梯子问题

爬梯子也是算法高频考点无疑了！

题目：你准备要爬楼梯。你面对的是一个 n 步可以走上去的楼梯。你每次可以走一步或者两步，那么你有几种不同的方式可以爬上去吗？

解：每次只能爬 1 步或 2 步，爬到第 n 层的方法要么是从第 n-1 层 1 步上来的，要不就是从 n-2 层 2 步上来的。采用递归！但要注意避免递归中运算重复的部分：

var temp = []
var climbStairs = function(n) {
    if(n <= 0){
        return 0
    }
    if(n <= 2){
        return n
    }
    if(temp[n]){
        return temp[n]
    }
    temp[n] = climbStairs(n-2) + climbStairs(n-1)
    return temp[n]
};

爬梯子问题又可称是 “斐波那契数列”。

斐波那契数列指的是这样一个数列从第3项开始，每一项都等于前两项之和，比如：1, 2, 3, 5, 8, 13, 21......，用到递归无疑了，但是一定要记得缓存递归项，否则会内存溢出（比如climbStairs(5)分解为climbStairs(3)和climbStairs(4)，climbStairs(4)又分解为climbStairs(2)和climbStairs(3)，这样就有两个重复的climbStairs(3)了）。

• 寻找最长公共子串

也称为 “LCS 问题”

leetcode#1143

var longestCommonSubsequence = function(text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        const c1 = text1[i - 1];
        for (let j = 1; j <= n; j++) {
            const c2 = text2[j - 1];
            if (c1 === c2) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
};

不过这个问题也勾起了本瓜当初面腾讯 WXG 的最后一题 leetcode#3 回忆。（OS：最长子串问题真的是必考！）

贪心法

贪心算法，即使你不怎么用，一定也听过它的大名！

最典型的例子有：旅行商问题（最短路径问题）（TSP）

之前有写过一篇关于最短路径问题的文章：《会一会改变世界的图算法——Dijkstra（狄克斯特拉）算法》。

与之最大不同的是，旅行商问题是一个 NP 问题，即只是一个近似算法，没有完全准确的解，所以需要尽可能的“贪心”。

题目：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

leetcode#847

回溯法

回溯算法和穷举法很像，都是树的深度优先遍历，但回溯法会进行'剪枝'，比如第 5 层某 i 叶子结点时发现该节点已经无意义，会直接跳过该节点下面的遍历，提高了效率。

回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

• 找到一个可能存在的正确的答案
• 在尝试了所有可能的分步方法后宣告该问题没有答案

在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

著名的是 八皇后问题。像这种棋盘问题也是高频考点。（面试腾讯 PCG 遇到过）

题目：在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后。为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。问，一共有多少情况可满足？

解： 由于一行只能有一个皇后，所以选择一行一行地填写皇后。在填第n行的皇后时不能与[0, n-1]行已填写的皇后在同一列、同一正对角线与反对角线上。若满足条件则继续递归，否则回溯重新选择下一列。

class Queen {
  constructor(num) {
    this.num = num;
    this.arr = [];
    this.result = [];
    this.initList();
    this.buildList(this.arr, 0);
  }

  initList() {// 设置 num * num 的矩形方阵
    let num = this.num;
    for (let i = 0; i < num; i++) {
      this.arr[i] = [];
      for (let j = 0; j < num; j++) {
        this.arr[i][j] = 0;
      }
    }
    console.log(this.arr);
  }

  buildList(list, row) {
    // 递归中止条件,找到一个解缓存起来
    if (row === list.length) {
      this.result.push(JSON.parse(JSON.stringify(list)));
      return;
    }
    for (let col = 0, len = list.length; col < len; col++) {
      if (this.isSafe(list, row, col)) {
        list[row][col] = 1; // 1 表示设置该位置有皇后
        this.buildList(list, row + 1);
        // 走到这里，说明该次递归已经结束，不管找没找到，都需要重置
        list[row][col] = 0;
      }
    }
  }

  isSafe(list, row, col) {
    const len = list.length;
    // 同一列
    for (let i = 0; i < len; i++) {
      if (list[i][col] === 1) return false;
    }
    // 斜右上方
    for (let i = row - 1, j = col + 1; i >= 0 && j < len; i--, j++) {
      if (list[i][j] === 1) return false;
    }
    // 斜左上方
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (list[i][j] === 1) return false;
    }
    return true;
  }
}
const queen = new Queen(8);
console.log(queen.result);

参考

面试题 08.12. 八皇后

分支限界法

还记得我们前文有提到的 01 背包问题吗？【分支限界法】也能求解 01 背包问题

^{难受啊胸dei！到这里有点被劝退的赶脚（QAQ），算法确实是计算机技术的护城河！！继续啃吧！}

概率算法

概率算法又大致分为四类：

1. 数值概率算法
2. 蒙特卡罗（Monte Carlo）算法
3. 拉斯维加斯（Las Vegas）算法
4. 舍伍德（Sherwood）算法

先混个眼熟吧......更多自行探索。

近似算法

前面提到过的旅行商问题也是近似算法。

更多可了解：P/NP问题，P/NP 问题是一个在理论信息学中计算复杂度理论领域里至今未被解决的问题，也是克雷数学研究所七个千禧年大奖难题之一。（哇！有一种触及人类数学天花板的错觉）

数据挖掘算法

数据挖掘算法底下又细分十大算法，更多：数据挖掘十大算法详解

本瓜先告辞，mark 一下，后面或许有空再来。

小结

以上笔试面试中常见的有：快排、最长子串问题系列、最短路径查找问题系列、棋盘问题系列、深度优先遍历系列、广度优秀遍历系列。

后面四种算法只需大致了解~

不过其中随处可见且最最核心的递归思想，真的太重要辣~

怎么说呢？

简单是最迷人的，这一点不会变。

算法确实很难，但或许难得东西，才有你让它变简单的价值吧~

我是掘金安东尼，公众号【掘金安东尼】，输出暴露输入，技术洞见生活。

大家端午安康！