前端面试必备——“算法设计与分析”

掘金安东尼 08-18 145

前言：

现时兄弟们对“拉斯维加斯算法的基本思想”可能比较关注，各位老铁们都需要分析一些“拉斯维加斯算法的基本思想”的相关文章。那么小编在网上搜集了一些对于“拉斯维加斯算法的基本思想””的相关文章，希望各位老铁们能喜欢，你们一起来了解一下吧！

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

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

分治法

分治法是建基于多项分支递归的一种很重要的算法范型。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

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

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

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

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));};

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

李永乐老师视频讲解动态规划法

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

动态规划（简称DP）背后的基本思想非常简单。即：大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

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

背包问题

背包问题的基础是【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]}

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

如果背包不放第 i 件物品，那么问题就转化为前 i-1 件物品放入容量为 v 的背包中，价值为 f[i-1][c]；如果放第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：最长子串问题真的是必考！）

贪心法

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

贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

最典型的例子有：旅行商问题（最短路径问题）（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），算法确实是计算机技术的护城河！！继续啃吧！

概率算法

概率算法也叫随机化算法。概率算法允许算法在执行过程中随机地选择下一个计算步骤。在很多情况下，算法在执行过程中面临选择时，随机性选择比最优选择省时，因此概率算法可以在很大程度上降低算法的复杂度。

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

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

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

近似算法