95% 的算法都是基于这 6 种算法思想

示例 2：

输入： 3

输出： 3

解释： 有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶

2. 1 阶 + 2 阶

3. 2 阶 + 1 阶

解法：动态规划

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

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

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

• 定义子问题

• 实现需要反复执行解决的子子问题部分

• 识别并求解出边界条件

第一步：定义子问题

如果用 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)

更多解答

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(n^3^)

• 空间复杂度：O(1)

解法二：动态规划

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

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

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

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

j

a a b a

i a ?

a ?

b ?

a ?

注意： 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(n^2^)

• 空间复杂度：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(n^2^)

• 空间复杂度：O(n^2^)

更多解答

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

《一线大厂 Java 面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》无偿开源 威信搜索公众号【编程进阶路】 * 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 ，都有一个胃口值 g~i~ ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 s~j~。如果 s~j~ >= g~i~ ，我们可以将这个饼干 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

示例 2：

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

输出: True

解释:

你可以分割出这样两个连续子序列 :

1, 2, 3, 4, 5

3, 4, 5

示例 3：

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

输出: False

提示：

• 输入的数组长度范围为 [1, 10000]

解法：贪心算法

从头开始，我们每次仅仅寻找满足条件的序列（连续子序列长度为 3），剔除之后，依次往后遍历：

• 判断当前元素是否能够拼接到前一个满足条件的连续子序列上，可以的话，则拼接

• 如果不可以，则判断以当前元素开始能否构成连续子序列（长度为 3），可以的话，则剔除连续子序列

• 否则，返回 false

const isPossible = function(nums) {

let max = nums[nums.length - 1]

// arr：存储原数组中数字每个数字出现的次数

// tail：存储以数字 num 结尾的且符合题意的连续子序列个数

let arr = new Array(max + 2).fill(0),

tail = new Array(max + 2).fill(0)

for(let num of nums) {

arr[num] ++

}

for(let num of nums) {

if(arr[num] === 0) continue

else if(tail[num-1] > 0){

tail[num-1]--

tail[num]++

}else if(arr[num+1] > 0 && arr[num+2] > 0){

arr[num+1]--

arr[num+2]--

tail[num+2]++

} else {

return false

}

arr[num]--

}

return true

}

复杂度分析：

• 时间复杂度：O(n)

• 空间复杂度：O(n)

更多解答

7.11 全排列问题

给定一个?没有重复?数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]

输出:

[

[1,2,3],

[1,3,2],

[2,1,3],

[2,3,1],

[3,1,2],

[3,2,1]

]

解法：回溯算法

本题是回溯算法的经典应用场景

1. 算法策略

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

2. 适用场景

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

3. 代码实现

我们可以写一下，数组 [1, 2, 3] 的全排列有：

• 先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]，即 1 + [2, 3] 的全排列；

• 再写以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]，即 2 + [1, 3] 的全排列；

• 最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列。

即回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

这显然是一个?递归?结构；

• 递归的终止条件是：一个排列中的数字已经选够了 ，因此我们需要一个变量来表示当前程序递归到第几层，我们把这个变量叫做 depth ，或者命名为 index ，表示当前要确定的是某个全排列中下标为 index 的那个数是多少；

• used（object）：用于把表示一个数是否被选中，如果这个数字(num)被选择这设置为 used[num] = true ，这样在考虑下一个位置的时候，就能够以 O(1)的时间复杂度判断这个数是否被选择过，这是一种「以空间换时间」的思想。

let permute = function(nums) {

// 使用一个数组保存所有可能的全排列

let res = []

if (nums.length === 0) {

return res

}

let used = {}, path = []

dfs(nums, nums.length, 0, path, used, res)

return res

}

let dfs = function(nums, len, depth, path, used, res) {

// 所有数都填完了

if (depth === len) {

res.push([...path])

return

}

for (let i = 0; i < len; i++) {

if (!used[i]) {

// 动态维护数组

path.push(nums[i])