95% 的算法都是基于这 6 种算法思想，毕向东 Java 教程百度云

关注

发布于: 2 小时前


while(low <= high) {
 if(elem < item) { // 比中间数高
  low = mid + 1
 } else if(elem > item) { // 比中间数低
  high = mid - 1
 } else { // 相等
     return mid
 }
}

复制代码

第三步：合并


function binarySearch(items, item) {
    var low = 0,
        high = items.length - 1,
        mid, elem
    while(low <= high) {
        mid = Math.floor((low+high)/2)
        elem = items[mid]
        if(elem < item) {
            low = mid + 1
        } else if(elem > item) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return -1
}

复制代码

最后，二分法只能应用于数组有序的情况，如果数组无序，二分查找就不能起作用了


function binarySearch(items, item) {
    // 快排
    quickSort(items)
    var low = 0,
        high = items.length - 1,
        mid, elem
    while(low <= high) {
        mid = Math.floor((low+high)/2)
        elem = items[mid]
        if(elem < item) {
            low = mid + 1
        } else if(elem > item) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return -1
}


// 测试
var arr = [2,3,1,4]
binarySearch(arr, 3)
// 2


binarySearch(arr, 5)
// -1

复制代码

测试成功

3 贪心算法

3.1 算法策略

贪心算法，故名思义，总是做出当前的最优选择，即期望通过局部的最优选择获得整体的最优选择。

某种意义上说，贪心算法是很贪婪、很目光短浅的，它不从整体考虑，仅仅只关注当前的最大利益，所以说它做出的选择仅仅是某种意义上的局部最优，但是贪心算法在很多问题上还是能够拿到最优解或较优解，所以它的存在还是有意义的。

3.2 适用场景

在日常生活中，我们使用到贪心算法的时候还是挺多的，例如：

从 100 章面值不等的钞票中，抽出 10 张，怎样才能获得最多的价值？

我们只需要每次都选择剩下的钞票中最大的面值，最后一定拿到的就是最优解，这就是使用的贪心算法，并且最后得到了整体最优解。

但是，我们任然需要明确的是，期望通过局部的最优选择获得整体的最优选择，仅仅是期望而已，也可能最终得到的结果并不一定不能是整体最优解。

例如：求取 A 到 G 最短路径：

根据贪心算法总是选择当前最优选择，所以它首先选择的路径是 AB，然后 BE、EG，所得到的路径总长为 1 + 5 + 4 = 10，然而这并不是最短路径，最短路径为 A->C->G : 2 + 2 = 4，所以说，贪心算法得到得并不一定是最优解。

那么一般在什么时候可以尝试选择使用贪心算法喃？

当满足一下条件时，可以使用：

原问题复杂度过高
求全局最优解的数学模型难以建立或计算量过大
没有太大必要一定要求出全局最优解，“比较优”就可以

如果使用贪心算法求最优解，可以按照以下 步骤求解 ：

首先，我们需要明确什么是最优解（期望）
然后，把问题分成多个步骤，每一步都需要满足：
可行性：每一步都满足问题的约束
局部最优：每一步都做出一个局部最优的选择
- 不可取消：选择一旦做出，在后面遇到任何情况都不可取消
最后，叠加所有步骤的最优解，就是全局最优解

3.3 经典案例：活动选择问题

使用贪心算法求解的经典问题有：

最小生成树算法
单源最短路径的 Dijkstra 算法
Huffman 压缩编码
背包问题
活动选择问题等

其中活动选择问题是最简单的，这里详细介绍这个。

活动选择问题是《算法导论》上的例子，也是一个非常经典的问题。有 n 个活动（a1,a2,…,an）需要使用同一个资源（例如教室），资源在某个时刻只能供一个活动使用。每个活动 ai 都有一个开始时间 si 和结束时间 fi 。一旦被选择后，活动 ai 就占据半开时间区间 [si,fi) 。如果 [si,fi) 和 [sj,fj) 互不重叠，ai 和 aj 两个活动就可以被安排在这一天。

该问题就是要安排这些活动，使得尽量多的活动能不冲突的举行。例如下图所示的活动集合 S，其中各项活动按照结束时间单调递增排序。

共有 7 个活动，它们在 18 个小时内需要占用的时间如上图，如何选择活动，能让这间教室利用率最高喃（能够举行更多的活动）？

贪心算法对这种问题的解决很简单的，它开始时刻开始选择，每次选择开始时间与与已选择活动不冲突的，结束时间又比较靠前的活动，这样会让剩下的时间区间更长。

首先 a1 活动的结束时间最早，选择 a1 活动
a1 结束后，a2 有时间冲突，不可选择，a3、a4 都可选择，但 a4 结束时间最早，选择 a4
依次选择时间没有冲突的，又结束时间最早的活动

最终选择活动为 a1，a4，a5，a7。为最优解。

4 回溯算法

4.1 算法策略

回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去，重新做出选择。深度优先搜索利用的就是回溯算法思想。

4.2 适用场景

回溯算法很简单，它就是不断的尝试，直到拿到解。它的这种算法思想，使它通常用于解决广度的搜索问题，即从一组可能的解中，选择一个满足要求的解。

4.3 使用回溯算法的经典案例

深度优先搜索
0-1 背包问题
正则表达式匹配
八皇后
数独
全排列

等等，深度优先搜索我们在图那一章已经介绍过，这里以正则表达式匹配为例，介绍一下

正则表达式匹配


var string = "abbc"
var regex = /ab{1,3}c/
console.log( string.match(regex) )
// ["abbc", index: 0, input: "abbc", groups: undefined]

复制代码

它的匹配过程：

在第 5 步匹配失败，此时 b{1,3} 已经匹配到了两个 b 正在尝试第三个 b ，结果发现接下来是 c 。此时就需要回溯到上一步， b{1,3} 匹配完毕（匹配到了 bb ），然后再匹配 c ，匹配到了 c 匹配结束。

5 动态规划

5.1 算法策略

动态规划也是将复杂问题分解成小问题求解的策略，与分治算法不同的是，分治算法要求各子问题是相互独立的，而动态规划各子问题是相互关联的。

所以，动态规划适用于子问题重叠的情况，即不同的子问题具有公共的子子问题，在这种情况下，分治策略会做出很多不必要的工作，它会反复求解那些公共子子问题，而动态规划会对每个子子问题求解一次，然后保存在表格中，如果遇到一致的问题，从表格中获取既可，所以它无需求解每一个子子问题，避免了大量的不必要操作。

5.2 适用场景

动态规划适用于求解最优解问题，比如，从面额不定的 100 个硬币中任意选取多个凑成 10 元，求怎样选取硬币才可以使最后选取的硬币数最少又刚好凑够了 10 元。这就是一个典型的动态规划问题。它可以分成一个个子问题（每次选取硬币），每个子问题又有公共的子子问题（选取硬币），子问题之间相互关联（已选取的硬币总金额不能超过 10 元），边界条件就是最终选取的硬币总金额为 10 元。

针对上例，也许你也可以说，我们可以使用回溯算法，不断的去试探，但回溯算法是使用与求解广度的解（满足要求的解），如果是用回溯算法，我们需要尝试去找所有满足条件的解，然后找到最优解，时间复杂度为 O(2n) ，这性能是相当差的。大多数适用于动态规划的问题，都可以使用回溯算法，只是使用回溯算法的时间复杂度比较高而已。

最后，总结一下，我们使用动态规划求解问题时，需要遵循以下几个重要步骤：

定义子问题
实现需要反复执行解决的子子问题部分
识别并求解出边界条件

5.3 使用动态规划求解的一些经典问题

爬楼梯问题：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
背包问题：给出一些资源（有总量及价值），给一个背包（有总容量），往背包里装资源，目标是在背包不超过总容量的情况下，装入更多的价值
硬币找零：给出面额不定的一定数量的零钱，以及需要找零的钱数，找出有多少种找零方案
图的全源最短路径：一个图中包含 u、v 顶点，找出从顶点 u 到顶点 v 的最短路径
最长公共子序列：找出一组序列的最长公共子序列（可由另一序列删除元素但不改变剩下元素的顺序实现）

这里以最长公共子序列为例。

爬楼梯问题

这里以动态规划经典问题爬楼梯问题为例，介绍求解动态规划问题的步骤。

第一步：定义子问题

如果用 dp[n] 表示第 n 级台阶的方案数，并且由题目知：最后一步可能迈 2 个台阶，也可迈 1 个台阶，即第 n 级台阶的方案数等于第 n-1 级台阶的方案数加上第 n-2 级台阶的方案数

第二步：实现需要反复执行解决的子子问题部分


dp[n] = dp[n?1] + dp[n?2]

复制代码

第三步：识别并求解出边界条件


// 第 0 级 1 种方案 
dp[0]=1 
// 第 1 级也是 1 种方案 
dp[1]=1

复制代码

最后一步：把尾码翻译成代码，处理一些边界情况


let climbStairs = function(n) {
    let dp = [1, 1]
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

复制代码

复杂度分析：

时间复杂度：O(n)
空间复杂度：O(n)

优化空间复杂度：


let climbStairs = function(n) {
    let res = 1, n1 = 1, n2 = 1
    for(let i = 2; i <= n; i++) {
        res = n1 + n2
        n1 = n2
        n2 = res
    }
    return res
}

复制代码

空间复杂度：O(1)

6 枚举算法

6.1 算法策略

枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的。

6.2 解题思路

确定枚举对象、枚举范围和判定条件。
逐一列举可能的解，验证每个解是否是问题的解。

7 刷题

7.1 爬楼梯问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：


输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

复制代码

示例 2：


输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

复制代码

解法：动态规划

动态规划（Dynamic Programming，DP）是一种将复杂问题分解成小问题求解的策略，但与分治算法不同的是，分治算法要求各子问题是相互独立的，而动态规划各子问题是相互关联的。

分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为子问题解的合并。

我们使用动态规划求解问题时，需要遵循以下几个重要步骤：

定义子问题
实现需要反复执行解决的子子问题部分
识别并求解出边界条件

第一步：定义子问题

第二步：实现需要反复执行解决的子子问题部分


dp[n] = dp[n?1] + dp[n?2]

复制代码

第三步：识别并求解出边界条件


// 第 0 级 1 种方案 
dp[0]=1 
// 第 1 级也是 1 种方案 
dp[1]=1

复制代码

最后一步：把尾码翻译成代码，处理一些边界情况


let climbStairs = function(n) {
    let dp = [1, 1]
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

复制代码

复杂度分析：

时间复杂度：O(n)
空间复杂度：O(n)

优化空间复杂度：


let climbStairs = function(n) {
    let res = 1, n1 = 1, n2 = 1
    for(let i = 2; i <= n; i++) {
        res = n1 + n2
        n1 = n2
        n2 = res
    }
    return res
}

复制代码

空间复杂度：O(1)

更多解答

7.2 使用最小花费爬楼梯

数组的每个索引作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i] (索引从 0 开始)。

每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。

您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。

示例 1:


输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。

复制代码

示例 2:


输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。

复制代码

注意：

cost 的长度将会在 [2, 1000] 。
每一个 cost[i] 将会是一个 Integer 类型，范围为 [0, 999] 。

解法：动态规划

本题注意理解题意：

第 i 级台阶是第 i-1 级台阶的阶梯顶部。
踏上第 i 级台阶花费 cost[i] ，直接迈一大步跨过而不踏上去则不用花费。
楼梯顶部在数组之外，如果数组长度为 len ，那么楼顶就在下标为 len

第一步：定义子问题

踏上第 i 级台阶的体力消耗为到达前两个阶梯的最小体力消耗加上本层体力消耗：

最后迈 1 步踏上第 i 级台阶： dp[i-1] + cost[i]
最后迈 1 步踏上第 i 级台阶： dp[i-2] + cost[i]

第二步：实现需要反复执行解决的子子问题部分

所以踏上第 i 级台阶的最小花费为：


dp[i] = min(dp[i-2], dp[i-1]) + cost[i]

复制代码

第三步：识别并求解出边界条件


// 第 0 级 cost[0] 种方案 
dp[0] = cost[0]
// 第 1 级，有两种情况
// 1：分别踏上第0级与第1级台阶，花费cost[0] + cost[1]
// 2：直接从地面开始迈两步直接踏上第1级台阶，花费cost[1]
dp[1] = min(cost[0] + cost[1], cost[1]) = cost[1]

复制代码

最后一步：把尾码翻译成代码，处理一些边界情况


let minCostClimbingStairs = function(cost) {
    cost.push(0)
    let dp = [], n = cost.length
    dp[0] = cost[0]
    dp[1] = cost[1]
    for(let i = 2; i < n; i++){
        dp[i] = Math.min(dp[i-2] , dp[i-1]) + cost[i]
    }
    return dp[n-1]
}

复制代码

复杂度分析：

时间复杂度：O(n)
空间复杂度：O(n)

优化：


let minCostClimbingStairs = function(cost) {
    let n = cost.length,
        n1 = cost[0],
        n2 = cost[1] 
    for(let i = 2;i < n;i++){
        let tmp = n2
        n2 = Math.min(n1,n2)+cost[i]
        n1 = tmp
    }
    return Math.min(n1,n2)
};

复制代码

时间复杂度：O(n)
空间复杂度：O(1)

更多解答

7.3 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:


输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

复制代码

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

第一步：定义子问题

动态规划是将整个数组归纳考虑，假设我们已经知道了以第 i-1 个数结尾的连续子数组的最大和 dp[i-1] ，显然以第 i 个数结尾的连续子数组的最大和的可能取值要么为 dp[i-1]+nums[i] ，要么就是 nums[i] 单独成一组，也就是 nums[i] ，在这两个数中我们取最大值

第二步：实现需要反复执行解决的子子问题部分


dp[n] = Math.max(dp[n?1]+nums[n], nums[n])

复制代码

第三步：识别并求解出边界条件


dp[0]=nums[0]

复制代码

最后一步：把尾码翻译成代码，处理一些边界情况

因为我们在计算 dp[i] 的时候，只关心 dp[i-1] 与 nums[i] ，因此不用把整个 dp 数组保存下来，只需设置一个 pre 保存 dp[i-1] 就好了。

代码实现（优化）：


let maxSubArray = function(nums) {
    let max = nums[0], pre = 0
    for(const num of nums) {
        if(pre > 0) {
            pre += num
        } else {
            pre = num
        }
        max = Math.max(max, pre)
    }
    return max
}

复制代码

复杂度分析：

时间复杂度：O(n)
空间复杂度：O(1)

7.4 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:


输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

复制代码

示例 2:


输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

复制代码

解法：动态规划

第一步：定义子问题

动态规划是将整个数组归纳考虑，假设我们已经知道了 i-1 个股票的最大利润为 dp[i-1] ，显然 i 个连续股票的最大利润为 dp[i-1] ，要么就是就是 prices[i] - minprice （ minprice 为前 i-1 支股票的最小值），在这两个数中我们取最大值

第二步：实现需要反复执行解决的子子问题部分


dp[i] = Math.max(dp[i?1], prices[i] - minprice)

复制代码

第三步：识别并求解出边界条件


dp[0]=0

复制代码

最后一步：把尾码翻译成代码，处理一些边界情况

因为我们在计算 dp[i] 的时候，只关心 dp[i-1] 与 prices[i] ，因此不用把整个 dp 数组保存下来，只需设置一个 max 保存 dp[i-1] 就好了。

代码实现（优化）：


let maxProfit = function(prices) {
    let max = 0, minprice = prices[0]
    for(let i = 1; i < prices.length; i++) {
        minprice = Math.min(prices[i], minprice)
        max = Math.max(max, prices[i] - minprice)
    }
    return max
}

复制代码

复杂度分析：

时间复杂度：O(n)
空间复杂度：O(1)

更多解答

7.5 回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：


输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"

复制代码

示例 2：


输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

复制代码

提示：

输入的字符串长度不会超过 1000 。

解法一：暴力法


let countSubstrings = function(s) {
  let count = 0
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      if (isPalindrome(s.substring(i, j + 1))) {
        count++
      }
    }
  }
  return count
}


let isPalindrome = function(s) {
  let i = 0, j = s.length - 1
  while (i < j) {
    if (s[i] != s[j]) return false
    i++
    j--
  }
  return true
}

复制代码

复杂度分析：

时间复杂度：O(n3)
空间复杂度：O(1)

解法二：动态规划

一个字符串是回文串，它的首尾字符相同，且剩余子串也是一个回文串。其中，剩余子串是否为回文串，就是规模小一点的子问题，它的结果影响大问题的结果。

我们怎么去描述子问题呢？

显然，一个子串由两端的 i 、 j 指针确定，就是描述子问题的变量，子串 s[i...j] （ dp[i][j] ）是否是回文串，就是子问题。

我们用二维数组记录计算过的子问题的结果，从 base case 出发，像填表一样递推出每个子问题的解。


 j
    a  a  b  a
i a :white_check_mark:
  a    :white_check_mark:  
  b       :white_check_mark:
  a          :white_check_mark:

复制代码

注意： i<=j ，只需用半张表，竖向扫描

所以：


i === j：dp[i][j]=true
j - i == 1 && s[i] == s[j]：dp[i][j] = true
j - i > 1 && s[i] == s[j] && dp[i + 1][j - 1]：dp[i][j] = true

复制代码

即：


s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1]): dp[i][j]=true

复制代码

否则为 false

代码实现：


let countSubstrings = function(s) {
  const len = s.length
  let count = 0
  const dp = new Array(len)


  for (let i = 0; i < len; i++) {
    dp[i] = new Array(len).fill(false)
  }
  for (let j = 0; j < len; j++) {
    for (let i = 0; i <= j; i++) {
      if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
        dp[i][j] = true
        count++
      } else {
        dp[i][j] = false
      }
    }
  }
  return count
}

复制代码

代码实现（优化）：

把上图的表格竖向一列看作一维数组，还是竖向扫描，此时仅仅需要将 dp 定义为一维数组即可


let countSubstrings = function(s) {
  const len = s.length
  let count = 0
  const dp = new Array(len)


  for (let j = 0; j < len; j++) {
    for (let i = 0; i <= j; i++) {
      if (s[i] === s[j] && (j - i <= 1 || dp[i + 1])) {
        dp[i] = true
        count++
      } else {
        dp[i] = false
      }
    }
  }
  return count;
}

复制代码

复杂度分析：

时间复杂度：O(n2)
空间复杂度：O(n)

更多解答

7.6 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：


输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

复制代码

示例 2：


输入: "cbbd"
输出: "bb"

复制代码

解法：动态规划

第 1 步：定义状态

dp[i][j] 表示子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，可以取到 s[i] 和 s[j] 。

第 2 步：思考状态转移方程

对于一个子串而言，如果它是回文串，那么在它的首尾增加一个相同字符，它仍然是个回文串


dp[i][j] = (s[i] === s[j]) && dp[i+1][j-1]

复制代码

第 3 步：初始状态：


dp[i][i] = true // 单个字符是回文串
if(s[i] === s[i+1]) dp[i][i+1] = true // 连续两个相同字符是回文串

复制代码

代码实现：


const longestPalindrome = (s) => {
  if (s.length < 2) return s
  // res: 最长回文子串
  let res = s[0], dp = []
  for (let i = 0; i < s.length; i++) {
    dp[i][i] = true
  }
  for (let j = 1; j < s.length; j++) {
    for (let i = 0; i < j; i++) {
      if (j - i === 1 && s[i] === s[j]) {
        dp[i][j] = true
      } else if (s[i] === s[j] && dp[i + 1][j - 1]) {
        dp[i][j] = true
      }   
      // 获取当前最长回文子串
      if (dp[i][j] && j - i + 1 > res.length) {
        res = s.substring(i, j + 1)
      }
    }
  }


  return res
}

复制代码

复杂度分析：

时间复杂度：O(n2)
空间复杂度：O(n2)

7.7 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：


输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

复制代码

示例 2：


输入：grid = [[1,2,3],[4,5,6]]
输出：12

复制代码

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

1、DP 方程当前项最小路径和 = 当前项值 + 上项或左项中的最小值 grid[i][j] += Math.min( grid[i - 1][j], grid[i][j - 1] )

2、边界处理 grid 的第一行与第一列分别没有上项与左项故单独处理计算起项最小路径和计算第一行：


for(let j = 1; j < col; j++) grid[0][j] += grid[0][j - 1]

复制代码

计算第一列：


for(let i = 1; i < row; i++) grid[i][0] += grid[i - 1][0]

复制代码

3、代码实现


var minPathSum = function(grid) {
    let row = grid.length, col = grid[0].length


    // calc boundary
    for(let i = 1; i < row; i++)
        // calc first col
        grid[i][0] += grid[i - 1][0]


    for(let j = 1; j < col; j++)
        // calc first row
        grid[0][j] += grid[0][j - 1]


    for(let i = 1; i < row; i++)
        for(let j = 1; j < col; j++)
            grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1])
    
    return grid[row - 1][col - 1]
};

复制代码

更多解答

7.8 买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:


输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

复制代码

示例 2:


输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

复制代码

示例 3:


输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

复制代码

提示：

1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

解法一：峰底买入，峰顶卖出

如图，在第二天买入，第三天卖出，第四天买入，第五天卖出获利最高，此处代码不再赘述，可以自己尝试写一下

解法二：贪心算法

贪心算法，故名思义，总是做出当前的最优选择，即期望通过局部的最优选择获得整体的最优选择。

对应于该题，第一天买入，第二天卖出，…，第 i 天买入，第 i+1 天卖出，如果 i 天买入第 i+1 天卖出有利润则买入，否则不买

第 i-1 天买入第 i 天卖出获利 prices[i+1]-prices[i] ，我们仅仅需要将 prices[i+1]-prices[i] 的所有正值加起来就是可获取的最大利益

代码实现：


let maxProfit = function(prices) {
    let profit = 0
    for (let i = 0; i < prices.length - 1; i++) {
        if (prices[i + 1] > prices[i]) {
            profit += prices[i + 1] - prices[i]
        }
    }
    return profit
}

复制代码

复杂度分析：

时间复杂度：O(n)
空间复杂度：O(1)

更多解答

7.9 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

注意：

你可以假设胃口值为正。一个小朋友最多只能拥有一块饼干。

示例 1:


输入: [1,2,3], [1,1]


输出: 1


解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

复制代码

示例 2:


输入: [1,2], [1,2,3]


输出: 2


解释: 
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

复制代码

解法：贪心算法


const findContentChildren = (g, s) => {
    if (!g.length || !s.length) return 0
    
    g.sort((a, b) => a - b)
    s.sort((a, b) => a - b)
    
    let gi = 0, si = 0
    while (gi < g.length && si < s.length) {
        if (g[gi] <= s[si++]) gi++
    }
    return gi
}

复制代码

更多解答

7.10 分割数组为连续子序列

给你一个按升序排序的整数数组 num （可能包含重复数字），请你将它们分割成一个或多个子序列，其中每个子序列都由连续整数组成且长度至少为 3 。

如果可以完成上述分割，则返回 true ；否则，返回 false 。

示例 1：


输入: [1,2,3,3,4,5]
输出: True
解释:
你可以分割出这样两个连续子序列 : 
1, 2, 3
3, 4, 5

复制代码

感受：

其实我投简历的时候，都不太敢投递阿里。因为在阿里一面前已经过了字节的三次面试，投阿里的简历一直没被捞，所以以为简历就挂了。

特别感谢一面的面试官捞了我，给了我机会，同时也认可我的努力和态度。对比我的面经和其他大佬的面经，自己真的是运气好。别人 8 成实力，我可能 8 成运气。所以对我而言，我要继续加倍努力，弥补自己技术上的不足，以及与科班大佬们基础上的差距。希望自己能继续保持学习的热情，继续努力走下去。

也祝愿各位同学，都能找到自己心动的 offer。

分享我在这次面试前所做的准备（刷题复习资料以及一些大佬们的学习笔记和学习路线），都已经整理成了电子文档，需要的朋友可以【点赞+关注】戳这里即可免费获取

发布于: 2 小时前阅读数: 3

Geek_f90455

关注

还未添加个人签名 2021.07.06 加入

还未添加个人简介

发布

暂无评论

创作场景

95% 的算法都是基于这 6 种算法思想，毕向东 Java 教程百度云

第三步：合并

3.1 算法策略

3.2 适用场景

3.3 经典案例：活动选择问题

4.1 算法策略

4.2 适用场景

4.3 使用回溯算法的经典案例

正则表达式匹配

5.1 算法策略

5.2 适用场景

5.3 使用动态规划求解的一些经典问题

爬楼梯问题

第一步：定义子问题

第二步：实现需要反复执行解决的子子问题部分

第三步：识别并求解出边界条件

最后一步：把尾码翻译成代码，处理一些边界情况

复杂度分析：

优化空间复杂度：

6.1 算法策略

6.2 解题思路

7.1 爬楼梯问题

示例 1：

示例 2：

解法：动态规划

第一步：定义子问题

第二步：实现需要反复执行解决的子子问题部分

第三步：识别并求解出边界条件

最后一步：把尾码翻译成代码，处理一些边界情况

复杂度分析：

优化空间复杂度：

7.2 使用最小花费爬楼梯

示例 1:

示例 2:

注意：

解法：动态规划

第一步：定义子问题

第二步：实现需要反复执行解决的子子问题部分

第三步：识别并求解出边界条件

最后一步：把尾码翻译成代码，处理一些边界情况

复杂度分析：

优化：

7.3 最大子序和

示例:

进阶:

第一步：定义子问题

第二步：实现需要反复执行解决的子子问题部分

第三步：识别并求解出边界条件

最后一步：把尾码翻译成代码，处理一些边界情况

代码实现（优化）：

复杂度分析：

7.4 买卖股票的最佳时机

示例 1:

示例 2:

解法：动态规划

第一步：定义子问题

第二步：实现需要反复执行解决的子子问题部分

第三步：识别并求解出边界条件

最后一步：把尾码翻译成代码，处理一些边界情况

代码实现（优化）：

复杂度分析：

7.5 回文子串

示例 1：

示例 2：

提示：

解法一：暴力法

复杂度分析：

解法二：动态规划

代码实现：

代码实现（优化）：

复杂度分析：

7.6 最长回文子串

示例 1：

示例 2：

解法：动态规划

第 1 步：定义状态

第 2 步：思考状态转移方程

第 3 步：初始状态：

代码实现：