案例

GodX...大约 35 分钟

爬楼梯(简)

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

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

示例 1：

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

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

解题

// 动态规划
var climbStairs = function(n) {
  	// 结果集
    let dp = [];
  	// 边界条件
    dp[0] = 1;
    dp[1] = 1;
    for(let i = 2;i <= n;i++) {
      	// 状态转移方程
        dp[i] = dp[i - 1] + dp[i -2]
    }
    return dp[n]
};

// 递归
var climbStairs = function (n) {
    if (n <= 1)
        return 1;
    if (n < 3)
        return n;
    return climbStairs(n - 1) + climbStairs(n - 2);
};

// 尾递归
var climbStairs = function (n) {
    return Fibonacci(n, 1, 1);
};


function Fibonacci(n, a, b) {
    if (n <= 1)
        return b;
    return Fibonacci(n - 1, b, a + b);
}

尾递归和一般的递归不同在对内存的占用，普通递归创建stack累积而后计算收缩，尾递归只会占用恒量的内存（和迭代一样）。

// 数学：斐波那契数列
var climbStairs = function(n) {
    const sqrt_5 = Math.sqrt(5);
    const fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2,n + 1);
    return Math.round(fib_n / sqrt_5);
};

买股票的最佳时机(简)

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

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

示例 2：

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

解题

// 动态规划
//时间复杂度O(n) 空间复杂度O(n)，dp数组第二维是常数
const maxProfit = function (prices) {
  let n = prices.length;
  let dp = Array.from(new Array(n), () => new Array(2));

  dp[0][0] = 0; //第0天不持有
  dp[0][1] = -prices[0]; //第0天持有

  for (let i = 1; i < n; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
    dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
  }
  
  return dp[n - 1][0];
};

// 一次遍历
var maxProfit = function (prices) {
    let j = 1;
    let res = 0;
    let min = prices[0];
    while (j < prices.length) {
        if (prices[j] < min) {
            min = prices[j];
        }
        if(min < prices[j] && res < (prices[j] - min)) {
            res = prices[j] - min
        }
        j++;
    }
    return res
};

// 代码简洁版
	var maxProfit = function (prices) {
	    if (prices.length === 0) return 0;
	    // 最低买点
	    let min = prices[0];
	    // 最大收入
	    let max = 0;
	    for (let p of prices) {
	        // 最佳买点，买入点最低
	        min = Math.min(min, p);
	        max = Math.max(max, p - min);
	    }
	
	    return max;
	};

打家劫舍(中)

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 400

解题思路

nums 是一个数组，表示每家房屋的金额。
dp 是一个数组，用于存储到当前房屋为止能偷窃的最大金额。dp[i] 表示到达第 i 家时能偷窃的最大金额。
dp[0] 被设置为 0，因为没有房屋时，你自然不能偷窃。
dp[1] 被设置为 nums[0]，因为只有一家房屋时，你只能偷这一家。
接下来的循环从 i = 2 开始，直到 nums.length。在这个循环中，对于每家房屋，你有两个选择：偷或者不偷。如果你选择偷，那么你只能加上前前一家房屋的最大金额（因为不能偷相邻的），即 dp[i-2] + nums[i-1]；如果你选择不偷，那么你的总金额就是前一家房屋的最大金额，即 dp[i-1]。因此，dp[i] 被设置为这两种选择的较大值。
最后，返回 dp[nums.length]，这表示到达最后一家房屋时能偷窃的最大金额。

这个算法的时间复杂度是 O(n)，其中 n 是 nums 数组的长度。

var rob = function(nums) {
    const dp = [];
    dp[0] = 0;
    dp[1] = nums[0];
    for(let i = 2; i <= nums.length; i++) {
        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
    }
    return dp[nums.length];
};

单词拆分（中）

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同

解题思路

初始化动态规划数组：
- dp是一个布尔数组，长度为s.length + 1。dp[i]将表示字符串s的前i个字符是否可以被wordDict中的单词分解。
- 我们将dp[0]初始化为true，因为空字符串总是可以被分解的（即没有单词）。
遍历字符串s：
- 外层循环for (let i = 1; i <= s.length; i++)遍历字符串s的每个位置，从第一个字符到最后一个字符。
检查所有可能的分解方式：
- 内层循环for (let j = 0; j < i; j++)遍历字符串s的前i个字符的所有可能起始位置j。
- 对于每个起始位置 j，我们检查两个条件：
  - dp[j]是否为true，即s的前j个字符是否可以被分解。
  - s.substring(j, i)是否在wordDict中，即从位置j到i的子字符串是否是一个有效的单词。
更新动态规划数组：
- 如果上述两个条件都满足，那么dp[i]被设置为true，表示从开始到位置i的子字符串可以被分解。
- 使用break语句跳出内层循环，因为我们已经找到了一个有效的分解方式。
返回结果：
- 最后，我们返回dp[s.length]，它表示整个字符串s是否可以被wordDict中的单词分解。

这个算法的关键在于它考虑了所有可能的分解方式，并且通过动态规划来避免重复计算，从而高效地解决问题。

var wordBreak = function (s, wordDict) {
    // 创建一个布尔数组dp，长度为s.length + 1，初始化所有值为false
    // dp[i]将表示字符串s的前i个字符是否可以被wordDict中的单词分解
    let dp = new Array(s.length + 1).fill(false);
    
    // dp[0]设置为true，因为空字符串总是可以被分解的
    dp[0] = true;

    // 遍历字符串s的每个位置，从第一个字符到最后一个字符
    for (let i = 1; i <= s.length; i++) {
        // 遍历字符串s的前i个字符的所有可能起始位置j
        for (let j = 0; j < i; j++) {
            // 检查两个条件：
            // 1. dp[j]是否为true，即s的前j个字符是否可以被分解
            // 2. s.substring(j, i)是否在wordDict中，即从位置j到i的子字符串是否是一个有效的单词
            if (dp[j] && wordDict.includes(s.substring(j, i))) {
                // 如果两个条件都满足，那么dp[i]设置为true
                dp[i] = true;
                // 使用break语句跳出内层循环，因为我们已经找到了一个有效的分解方式
                break;
            }
        }
    }

    // 返回dp[s.length]，它表示整个字符串s是否可以被wordDict中的单词分解
    return dp[s.length];
};

零钱兑换（中）

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

解题思路

F(i)=min_j=0…n−1F(i−c_j)+1

其中c，代表的是第」枚硬币的面值，即我们枚举最后一枚硬币面额是G，那么需从i一c这个金额的状态 F（i一c_j）转移过来，再算上枚举的这枚硬币数量 1 的贡献，由于要硬币数量最少，所以 F（i）为前面能转移过来的状态的最小值加上枚举的硬币数量 1。

var coinChange = function (coins, amount) {
    let max = amount + 1;
    let dp = new Array(max).fill(max);
    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
        for (let j = 0; j < coins.length; j++) {
            if (coins[j] <= i) {
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
};

最长递增子序列（中）

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

进阶：

你能将算法的时间复杂度降低到 O(n log(n)) 吗?

解题思路

初始化:
- var lengthOfLIS = function(nums)：这是一个函数定义，接受一个数组nums作为参数。
- const len = nums.length;：获取数组的长度并存储在变量len中。
- const dp = new Array(len).fill(1);：创建一个新数组dp，其长度与nums相同，并用1填充。这个数组将用于存储到当前位置为止的最长递增子序列的长度。
动态规划:
- for(let i = 0; i < len;i++) { ... }：这是一个外层循环，遍历数组中的每个元素。
- for(let j = 0;j < i;j++) { ... }：这是一个内层循环，遍历当前元素之前的所有元素。
- if(nums[i] > nums[j]) { ... }：如果当前元素大于之前的某个元素，则执行以下操作：
  - dp[i] = Math.max(dp[i],dp[j] + 1)：更新dp[i]的值为dp[j] + 1和当前dp[i]的较大值。这表示以nums[i]结尾的最长递增子序列可以包括nums[j]，并且长度增加1。
返回结果:
- return Math.max(...dp)：返回dp数组中的最大值，这个值就是最长递增子序列的长度。
  这个算法的核心思想是动态规划。对于数组中的每个元素，它都考虑了所有可能的递增子序列，并选择了最长的那个。通过这种方式，它能够找到整个数组的最长递增子序列。

var lengthOfLIS = function(nums) {
    const len = nums.length;
    const dp = new Array(len).fill(1);

    for(let i = 0; i < len;i++) {
        for(let j = 0;j < i;j++) {
            if(nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i],dp[j] + 1)
            }
        }
    }
    return Math.max(...dp)
};

三角形最小路径和(中)

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是下标与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

提示：

1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104

进阶：

你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

解题思路

首先，我们要解决的问题是在一个由数字组成的三角形中找到一条从顶部到底部的路径，使得路径上的数字之和最小。这个三角形看起来像这样：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

在这个例子中，最小的路径和是从2 -> 3 -> 5 -> 1，总和是11。
现在，让我们来看看代码是如何工作的：

初始化动态规划数组：
- let n = triangle.length; 这行代码获取三角形的行数。
- let dp = new Array(n + 1).fill(0); 这行代码创建了一个新的数组dp，长度比三角形的高度多1，并用0填充。这个数组将用于存储到达每一行的每个位置的最小路径和。
遍历三角形：
- for (let i = n - 1; i >= 0; i--) { 这个循环从三角形的倒数第二行开始，向上遍历，直到第一行。
- for (let j = 0; j <= i; j++) { 这个循环遍历当前行的每个元素。
更新动态规划数组：
- dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j]; 这行代码是关键。它计算到达当前位置(i, j)的最小路径和。Math.min(dp[j], dp[j + 1])选择从当前位置向上移动时到达的两个可能位置(i-1, j)和(i-1, j-1)中的较小路径和。然后，我们加上当前位置的值triangle[i][j]。
计算结果：
- return dp[0]; 最后，我们返回动态规划数组的第一个元素，这是从顶部到底部的最小路径和。

这个算法之所以有效，是因为它从底部开始向上计算，每次都为上一行提供了到达底部最小路径和的必要信息。这样，当我们到达顶部时，dp[0]就包含了从顶部到底部的最小路径和。

为什么要构建一个长度为 n+1 的结果集？

在这个问题中，构建一个长度为n+1的结果集（在JavaScript中是dp数组）是为了简化计算过程，并处理边界情况。

简化计算：当我们从三角形的倒数第二行开始向上计算时，对于每一行的每个元素，我们需要考虑到达它的两个可能路径：直接从它下面的元素来，或者从它右下角的元素来。通过构建一个长度为n+1的结果集，我们可以确保在计算每一行的元素时，dp[j+1]总是存在的，即使是在最右边界的元素。这样，我们可以使用相同的逻辑来处理每一行的所有元素，而不需要特殊处理边界情况。
处理边界情况：在三角形的每一行中，最右边的元素没有右下角的元素，因此它只能从它正下方的元素到达。使用n+1长度的结果集，我们可以确保在计算最右边界的元素时，dp[j+1]是一个有效且初始化为0的元素。这样，当我们计算Math.min(dp[j], dp[j + 1])时，对于最右边界的元素，dp[j+1]实际上就是一个不会影响结果的0。
简化初始化：使用n+1长度的结果集也简化了初始化过程。我们可以使用new Array(n + 1).fill(0)来创建一个所有元素都初始化为0的数组，而不需要单独处理数组的第一个和最后一个元素。

总的来说，构建一个长度为n+1的结果集是为了使代码更简洁、更易于理解，并且减少处理边界情况的复杂性。

function minimumTotal(triangle) {
    let n = triangle.length;
    let dp = new Array(n + 1).fill(0);

    for (let i = n - 1; i >= 0; i--) {
        for (let j = 0; j <= i; j++) {
            dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j];
        }
    }

    return dp[0];
}

最小路径和（中）

给定一个包含非负整数的 *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] <= 200

解题思路

在动态规划中，边界条件通常需要特别考虑，因为它们没有左侧或上侧的邻居单元格，这意味着我们不能使用标准的递推关系来计算它们的值。
具体来说，这个算法中的边界处理如下：

第一行和第一列的起始点 (i === 0 && j === 0)：这个点是路径的起点，因此它的值就是网格中该点的原始值。在算法中，这个点被特别处理，通过 continue 语句跳过，因为它的值不需要改变。
第一行 (i === 0)：对于第一行的每个单元格，我们只能从左边的单元格到达它，因此它的最小路径和就是它左边单元格的最小路径和加上它自己的值。在代码中，这通过 dp[i][j] = dp[i][j - 1] + grid[i][j]; 实现。
第一列 (j === 0)：对于第一列的每个单元格，我们只能从上面的单元格到达它，因此它的最小路径和就是它上面单元格的最小路径和加上它自己的值。在代码中，这通过 dp[i][j] = dp[i - 1][j] + grid[i][j]; 实现。
其他单元格：对于不在第一行和第一列的单元格，我们可以从它上面的单元格或左边的单元格到达它。因此，它的最小路径和是它上面单元格和左边单元格的最小路径和中的较小值加上它自己的值。在代码中，这通过 dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; 实现。

通过这种方式，算法能够正确地计算出每个单元格的最小路径和，最终得到从左上角到右下角的最小路径和。

var minPathSum = function (grid) {
    const dp = grid;
    const m = grid.length, n = grid[0].length;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // 处理第一行和第一列的情况
            if (i === 0 && j === 0) {
                continue;
            } else if (i === 0) {
                dp[i][j] = dp[i][j - 1] + grid[i][j];
            } else if (j === 0) {
                dp[i][j] = dp[i - 1][j] + grid[i][j];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
    }

    return dp[m - 1][n - 1];
};

不同路径 II（中）

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

解题思路

该算法的设计利用了一个重要的观察：在每一步中，我们只关心到达当前列的路径数量，而不是每个格子的路径数量。
这里的关键在于，当我们从左到右遍历每一列时，我们实际上是在逐步构建到达每一列的路径数量。对于每一列，我们考虑的是从它左侧来的路径数量（如果左侧没有障碍物），以及它自身的路径数量（如果它上方没有障碍物）。这样，当我们到达一列的最后一个格子时，我们就已经考虑了从上方来的所有路径。

让我们通过一个例子来更清楚地说明这一点：
假设我们有一个3x3的网格，没有障碍物：

[
  [0, 0, 0],
  [0, 0, 0],
  [0, 0, 0]
]

我们用f[j]表示到达第j列的路径数量。我们从左到右遍历每一列：

第一列：只有一个格子，所以f[0] = 1。
第二列：有两个格子。到达第二列的第一个格子的路径数量是从第一列的第一个格子来的，所以f[1] = f[0] = 1。到达第二列的第二个格子的路径数量是从第二列的第一个格子来的（向右移动）加上从第一列的第二个格子来的（向下移动）。但由于我们只关心到达每一列的路径数量，我们只需要考虑从左侧来的路径数量，即f[1]。因此，第二列的路径数量仍然是1。
第三列：有三个格子。到达第三列的每个格子的路径数量都是从前一列的对应格子来的（向右移动）。因此，f[2] = f[1] = 1。
最终，f[2]将包含到达右下角的所有可能路径的数量，即1。

这个算法的关键在于，它通过只考虑到达每一列的路径数量，而不是每个格子的路径数量，来简化问题。这样，当我们到达一列的最后一个格子时，我们已经考虑了从上方来的所有路径。这种方法不仅简化了问题，还减少了所需的内存空间。

function uniquePathsWithObstacles(obstacleGrid) {
    // 获取网格的行数和列数
    const m = obstacleGrid.length, n = obstacleGrid[0].length;
    // 创建一个长度为n的数组，用于存储到达每一列的路径数量
    const f = new Array(n).fill(0);

    // 如果起点没有障碍物，则设置起点路径数量为1
    f[0] = obstacleGrid[0][0] === 0 ? 1 : 0;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            // 如果当前格子有障碍物，则路径数量为0，并继续下一个循环
            if (obstacleGrid[i][j] === 1) {
                f[j] = 0;
                continue;
            }
            // 如果左侧格子没有障碍物，则当前格子的路径数量等于左侧格子的路径数量加上当前格子的路径数量
            if (j - 1 >= 0 && obstacleGrid[i][j - 1] === 0) {
                f[j] += f[j - 1];
            }
        }
    }

    // 返回到达终点的路径数量
    return f[n - 1];
}

最长回文子串（中）

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

解题思路

中心扩展算法

中心扩展算法是一种用于寻找最长回文子串的简单而直观的算法。它的基本思想是从每个可能的中心开始，向两边扩展，以寻找最长的回文子串。这里的“中心”可以是字符串中的任意一个字符（对于奇数长度的回文子串）或任意两个相邻字符之间的空隙（对于偶数长度的回文子串）。

下面是中心扩展算法的详细步骤：

初始化：
- 设置两个变量 start 和 end 来记录最长回文子串的起始和结束位置。
- 设置一个辅助函数 expandAroundCenter(s, left, right)，用于从中心 left 和 right 开始扩展，并返回以 left 和 right 为中心的回文子串的长度。
遍历字符串：
- 遍历字符串 s 中的每个字符。
- 对于每个字符 s[i]，执行以下操作：
  - 以 s[i] 为中心，调用 expandAroundCenter(s, i, i) 来寻找奇数长度的回文子串。
  - 以 s[i] 和 s[i+1] 为中心，调用 expandAroundCenter(s, i, i+1) 来寻找偶数长度的回文子串。
  - 取两种情况中的最大值，如果这个值大于 end - start，则更新 start 和 end。
返回结果：
- 在遍历结束后，start 和 end 将记录最长回文子串的起始和结束位置。
- 返回 s.substring(start, end + 1) 作为最长回文子串。

Manacher’s 算法

Manacher’s 算法是一种用于寻找最长回文子串的高效算法，它的时间复杂度是 O(n)，其中 n 是字符串的长度。这个算法的关键在于它利用了回文串的对称性质，从而避免了不必要的比较，使得每个字符最多被比较一次。

算法步骤：

预处理：
- 在字符串的首尾和每个字符之间插入一个特殊字符（如 #），以消除奇数长度和偶数长度回文串的区别。例如，字符串 “abba” 被转换为 “^#a#b#b#a#$”。
- 新字符串的长度变为原来的两倍加一。
初始化：
- 创建一个数组 p，其中 p[i] 表示以 s[i] 为中心的回文子串向右扩展的长度（不包括 s[i] 本身）。
- 设置两个变量 center 和 right，分别表示当前找到的最长回文子串的中心和右边界。
遍历字符串：
- 对于新字符串中的每个字符 s[i]（从第二个字符开始），执行以下操作：
  - 如果 i 在 right 的左边，利用对称性质，设置 p[i] 的初始值为 min(p[2 * center - i], right - i)。
  - 试图扩展以 s[i] 为中心的回文子串，更新 p[i]。
  - 如果 i + p[i] 大于 right，更新 center 和 right。
找到最长回文子串：
- 在遍历结束后，p 数组中的最大值即为最长回文子串的长度。
- 通过 p 数组找到最长回文子串的中心位置和长度。
返回结果：
- 根据最长回文子串的中心位置和长度，从原始字符串中提取出最长回文子串。

中心扩展算法

function longestPalindrome(s) {
    if (s.length < 2) return s;

    let start = 0, end = 0;
    for (let i = 0; i < s.length; i++) {
        let len1 = expandAroundCenter(s, i, i);
        let len2 = expandAroundCenter(s, i, i + 1);
        let len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - Math.floor((len - 1) / 2);
            end = i + Math.floor(len / 2);
        }
    }
    return s.substring(start, end + 1);
}

function expandAroundCenter(s, left, right) {
    let L = left, R = right;
    while (L >= 0 && R < s.length && s[L] === s[R]) {
        L--;
        R++;
    }
    return R - L - 1;
}

Manacher’s 算法

function longestPalindrome(s) {
    if (s.length < 2) return s;

    let str = preprocess(s);
    let n = str.length;
    let p = new Array(n).fill(0);
    let center = 0, right = 0;

    for (let i = 1; i < n - 1; i++) {
        let mirror = 2 * center - i;

        if (right > i) {
            p[i] = Math.min(right - i, p[mirror]);
        }

        while (str[i + 1 + p[i]] === str[i - 1 - p[i]]) {
            p[i]++;
        }

        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }

    let maxLen = 0, centerIndex = 0;
    for (let i = 1; i < n - 1; i++) {
        if (p[i] > maxLen) {
            maxLen = p[i];
            centerIndex = i;
        }
    }

    return s.substring((centerIndex - maxLen) / 2, (centerIndex + maxLen) / 2);
}

function preprocess(s) {
    let sb = '^';
    for (let i = 0; i < s.length; i++) {
        sb += '#';
        sb += s[i];
    }
    sb += '#$';
    return sb;
}

交错字符串（中）

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。

两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会被分割成若干非空子字符串：

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
交错是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：a + b 意味着字符串 a 和 b 连接。

示例 1：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true

示例 2：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false

示例 3：

输入：s1 = "", s2 = "", s3 = ""
输出：true

提示：

0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1、s2、和 s3 都由小写英文字母组成

**进阶：**您能否仅使用 O(s2.length) 额外的内存空间来解决它?

解题思路

初始化数组 f:
- f 是一个布尔数组，长度为 s2.length + 1，初始值都为 false。
- 这个数组用于存储中间结果，f[j] 表示 s3 的前 i+j 个字符是否可以由 s1 的前 i 个字符和 s2 的前 j 个字符交错组成。
检查长度:
- 如果 s1、s2 和 s3 的长度之和不相等，那么 s3 显然不能由 s1 和 s2 交错组成，直接返回 false。
动态规划过程:
- f[0] 被设置为 true，表示空字符串可以由两个空字符串交错组成。
- 接下来，使用两层循环遍历 s1 和 s2。
- 对于每一对字符 s1[i-1] 和 s2[j-1]，更新数组 f：
  - 如果 i > 0（即 s1 中还有字符），则检查 s1[i-1] 是否等于 s3 中的当前字符（即 s3[p]），如果是，则更新 f[j]。
  - 如果 j > 0（即 s2 中还有字符），则检查 s2[j-1] 是否等于 s3 中的当前字符，如果是，则更新 f[j]。
返回结果:
- 最后，返回 f[m]，即 s3 是否可以由 s1 和 s2 交错组成。

这个函数使用了动态规划的思想，通过保存中间结果来避免重复计算，从而提高效率。希望这个解释能帮助你理解这段代码！

function isInterleave(s1, s2, s3) {
        let n = s1.length, m = s2.length, t = s3.length;

        if (n + m !== t) {
            return false;
        }

        let f = new Array(n + 1).fill(null).map(() => new Array(m + 1).fill(false));

        f[0][0] = true;
        for (let i = 0; i <= n; ++i) {
            for (let j = 0; j <= m; ++j) {
                let p = i + j - 1;
                if (i > 0) {
                    f[i][j] = f[i][j] || (f[i - 1][j] && s1[i - 1] === s3[p]);
                }
                if (j > 0) {
                    f[i][j] = f[i][j] || (f[i][j - 1] && s2[j - 1] === s3[p]);
                }
            }
        }

        return f[n][m];
    }

滚动数组优化

function isInterleave(s1, s2, s3) {
    // 创建一个布尔数组f，长度为s2.length + 1，所有值初始化为false
    let f = new Array(s2.length + 1).fill(false);

    // 获取s1, s2, s3的长度
    let n = s1.length, m = s2.length, t = s3.length;

    // 如果s1和s2的长度之和不等于s3的长度，则s3不能由s1和s2交错组成
    if (n + m !== t) {
        return false;
    }

    // f[0]设置为true，表示空字符串可以由两个空字符串交错组成
    f[0] = true;
    
    // 遍历s1和s2
    for (let i = 0; i <= n; ++i) {
        for (let j = 0; j <= m; ++j) {
            // 计算当前在s3中的位置
            let p = i + j - 1;
            
            // 如果i大于0（即s1中还有字符），检查s1[i-1]是否等于s3[p]
            if (i > 0) {
                f[j] = f[j] && s1[i - 1] === s3[p];
            }
            
            // 如果j大于0（即s2中还有字符），检查s2[j-1]是否等于s3[p]
            if (j > 0) {
                // 使用逻辑或更新f[j]，如果s2[j-1]等于s3[p]，则f[j]为true
                f[j] = f[j] || (f[j - 1] && s2[j - 1] === s3[p]);
            }
        }
    }

    // 返回f[m]，即s3是否可以由s1和s2交错组成
    return f[m];
}

编辑距离（中）

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

解题思路

初始化DP数组：创建一个二维数组 D，其大小为 (n+1) x (m+1)，其中 n 和 m 分别是两个字符串的长度。这个数组的目的是存储中间计算结果。
边界状态：D[i][0] 表示从字符串 word1 的前 i 个字符转换成空字符串所需的最小操作数，这显然就是 i（删除 i 个字符）。同理，D[0][j] 表示从空字符串转换成 word2 的前 j 个字符所需的最小操作数，即 j。
计算DP值：对于 D 数组的每个位置 D[i][j]，我们考虑以下三种情况：
- 从左边的元素来：D[i-1][j] + 1，这表示从 word1 的前 i-1 个字符转换到 word2 的前 j 个字符，然后删除 word1 的第 i 个字符。
- 从上面的元素来：D[i][j-1] + 1，这表示从 word1 的前 i 个字符转换到 word2 的前 j-1 个字符，然后在 word1 中插入 word2 的第 j 个字符。
- 从左上角的元素来：D[i-1][j-1]，这表示从 word1 的前 i-1 个字符转换到 word2 的前 j-1 个字符，然后检查 word1 的第 i 个字符和 word2 的第 j 个字符是否相同。如果不同，需要替换一个字符，因此结果加一。
取最小值：对于每个 D[i][j]，我们取这三种情况的最小值作为其值。
返回结果：D[n][m] 就是将整个 word1 转换为整个 word2 所需的最小操作数。

以 "horse" 和 "ros" 为例，最终 D[5][3] 的值将是 3，表示需要 3 步操作将 "horse" 转换为 "ros"。

function minDistance(word1, word2) {
    let n = word1.length;
    let m = word2.length;

    // 如果有一个字符串为空，则编辑距离为另一个字符串的长度
    if (n * m == 0) {
        return n + m;
    }

    // 初始化DP数组
    let D = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));

    // 初始化边界状态
    for (let i = 0; i <= n; i++) {
        D[i][0] = i;
    }
    for (let j = 0; j <= m; j++) {
        D[0][j] = j;
    }

    // 计算所有DP值
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            let left = D[i - 1][j] + 1;
            let down = D[i][j - 1] + 1;
            let left_down = D[i - 1][j - 1];
            if (word1[i - 1] != word2[j - 1]) {
                left_down += 1;
            }
            D[i][j] = Math.min(left, Math.min(down, left_down));
        }
    }
    return D[n][m];
}

买卖股票的最佳时机 III(难)

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

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

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

示例 1:

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

示例 2：

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

示例 3：

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

示例 4：

输入：prices = [1]
输出：0

提示：

1 <= prices.length <= 105
0 <= prices[i] <= 105

// 定义一个函数，用来计算最大利润
var maxProfit = function (prices) {
    const n = prices.length; // 获取价格数组的长度
    let buy1 = -prices[0], buy2 = -prices[0]; // 初始化第一次和第二次买入的最大利润为第一天的价格负值
    let sell1 = 0, sell2 = 0; // 初始化第一次和第二次卖出的最大利润为0

    // 遍历价格数组，从第二天开始
    for (let i = 1; i < n; i++) {
        // 更新第一次买入的最大利润
        buy1 = Math.max(buy1, -prices[i]);
        // 更新第一次卖出的最大利润
        sell1 = Math.max(sell1, buy1 + prices[i]);
        // 更新第二次买入的最大利润
        buy2 = Math.max(buy2, sell1 - prices[i]);
        // 更新第二次卖出的最大利润
        sell2 = Math.max(sell2, buy2 + prices[i]);
    }

    // 返回进行了最多两次交易后的最大利润
    return sell2;
};

function maxProfit(prices) {
    // 创建两个数组，buy和sell，长度都是3。
    // buy数组用于存储在买入股票时的最大利润，初始化为最小安全整数值。
    // sell数组用于存储在卖出股票时的最大利润，初始化为0。
    let buy = new Array(3).fill(Number.MIN_SAFE_INTEGER);
    let sell = new Array(3).fill(0);

    // 遍历价格数组
    for (let i of prices) {
        // 内部循环，用于处理买入和卖出的操作
        for (let j = 1; j < 3; j++) {
            // 计算在买入第j次时的最大利润
            // 即在前一次卖出时的利润减去当前价格
            buy[j] = Math.max(buy[j], sell[j - 1] - i);
            // 计算在卖出第j次时的最大利润
            // 即在前一次买入时的利润加上当前价格
            sell[j] = Math.max(sell[j], buy[j] + i);
        }
    }

    // 函数返回卖出股票的最大利润，即sell数组的最后一个元素
    return sell[2];
}

最大正方形（中）

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 '0' 或 '1'

解题思路

这个问题的关键在于理解如何通过已知的较小正方形来确定较大正方形的边长。对于矩阵中的每个位置(i, j)，如果matrix[i][j]是'1'，那么我们想要知道以(i, j)为右下角的最大正方形的边长。这个正方形的边长取决于它的左边、上边和左上角三个相邻位置的最大正方形边长。
这里的关键观察是，如果(i, j)是'1'，那么它的左边、上边和左上角也必须是'1'，否则(i, j)就不能成为更大正方形的一部分。因此，我们可以通过检查这三个相邻位置的最大正方形边长来确定(i, j)位置的最大正方形边长。
为什么我们要取这三个位置的最小值加1呢？这是因为正方形的特性要求它的所有边长都相等。如果我们想要构建一个以(i, j)为右下角的新正方形，那么这个新正方形的边长不能超过左边、上边和左上角三个位置的最小正方形边长。这是因为如果其中一个方向的最大正方形边长较小，那么在(i, j)位置扩展出来的正方形也会受到这个较小边长的限制。
例如，假设dp[i-1][j]（上边）的最大正方形边长是2，而dp[i][j-1]（左边）和dp[i-1][j-1]（左上角）的最大正方形边长都是3。这意味着在(i, j)位置向上扩展2个单位是安全的，因为上边有2个连续的'1'。但是，我们不能扩展到3个单位，因为那样会超出上边的'1'的范围。因此，以(i, j)为右下角的最大正方形边长就是2+1=3。
通过这种方式，我们可以确保dp[i][j]存储的是以(i, j)为右下角的最大正方形的边长。这个动态规划的方法允许我们高效地计算出整个矩阵中的最大正方形边长，而不需要重复计算。

function maximalSquare(matrix) {
    if (matrix.length === 0) return 0;
    let maxLen = 0;
    const m = matrix.length;
    const n = matrix[0].length;
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (matrix[i - 1][j - 1] === '1') {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
                maxLen = Math.max(maxLen, dp[i][j]);
            }
        }
    }

    return maxLen * maxLen;
}

昵称

邮箱

网址

按正序
按倒序
按热度

案例

爬楼梯(简)

买股票的最佳时机(简)

打家劫舍(中)

单词拆分（中）

零钱兑换（中）

最长递增子序列（中）

三角形最小路径和(中)

最小路径和（中）

不同路径 II（中）

最长回文子串（中）

交错字符串（中）

编辑距离（中）

买卖股票的最佳时机 III(难)

最大正方形（中）

预览: