移除元素

给你一个数组 nums* 和一个值 val，你需要 原地 移除所有数值等于 val *的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    const len = nums.length;
    let count = len;
    for(let i=len; i>=0; i--) {
        if(nums[i] === val) {
            nums.splice(i, 1);
            nums.push('_')
            count--;
        }
    }
    return count;
};

注意点（反向遍历，如果用splice(index, 1)）

关键问题：当连续出现多个 val 时，正向遍历会因为 splice() 修改数组长度和索引导致漏删。以下是详细分析和修正方案：

问题分析

代码可能的缺陷

1
2
3
4
5
6
7

for(let i=0; i<len; i++) {
    if(nums[i] === val) {
        nums.splice(i, 1); // 删除后，后续元素会前移
        nums.push('_');
        count--;
    }
}

• Bug 场景：若 nums = [3, 2, 2, 3], val = 2：
  1. 当 i=1 时，删除 nums[1]=2 → 数组变为 [3, 2, 3, '_']
  2. 下一轮 i=2，此时 nums[2]=3，漏掉了前移的 2。

根本原因

• splice() 会改变原数组长度和索引，但循环仍按原长度 len 执行。
• 删除元素后未调整索引 i，导致跳过后续元素检查。

其他方案

双指针（更高效）

1
2
3
4
5
6
7
8
9
10
11
12

var removeElement = function(nums, val) {
    let left = 0;
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] !== val) {
            nums[left] = nums[right];
            left++;
        }
    }
    // 可选：补位 '_'
    while (left < nums.length) nums[left++] = '_';
    return left;
};

优点：一次遍历完成删除和补位。

双指针解法图解（LeetCode 27. 移除元素）

双指针法核心思想

• 快指针（right）：遍历原数组，寻找保留元素。
• 慢指针（left）：指向下一个保留元素的存放位置。

双指针图解示例

输入：nums = [3, 2, 2, 3], val = 2
输出：[3, 3, _, _]（新长度为 2）

步骤 1：初始化指针

nums = [3, 2, 2, 3]
       ↑ ↑
       l r (left=0, right=0)

步骤 2：right=0，nums[0]=3 ≠ val

• 保留 nums[0]，复制到 nums[left]。

• left 和 right 同时右移：

  nums = [3, 2, 2, 3] (未修改)
  ↑ ↑
  l r (left=1, right=1)

步骤 3：right=1，nums[1]=2 == val

• 跳过不保留，仅 right 右移：

  nums = [3, 2, 2, 3]
  ↑ ↑
  l r (left=1, right=2)

步骤 4：right=2，nums[2]=2 == val

• 跳过不保留，仅 right 右移：

  nums = [3, 2, 2, 3]
  ↑ ↑
  l r (left=1, right=3)

步骤 5：right=3，nums[3]=3 ≠ val

• 保留 nums[3]，复制到 nums[left]。

• left 和 right 同时右移：

  nums = [3, 3, 2, 3] (left=2, right=4)
  ↑ ↑
  l r

循环结束

• right 越界，终止循环。
• 新长度：left = 2（前 left 个元素为有效结果）。

可选补位

1
2
3

for (let i = left; i < nums.length; i++) {
    nums[i] = '_'; // 补位
}

最终数组：

nums = [3, 3, '_', '_']

关键点总结

1. **快指针 right**：无脑向前扫描，检查每个元素。
2. **慢指针 left**：只接收不等于 val 的元素。
3. 补位：在返回新长度后，将剩余位置填充 _（按题目需求）。

这种方法保证了 O(n) 时间和 O(1) 空间，是最优解。

爬楼梯

1. 问题本质分析

• 问题描述：每次可以爬 1 或 2 个台阶，求爬到第 n 阶的方法数。
• 实际意义：该问题等价于 斐波那契数列，因为：
  • 到达第 n 阶的方法数 = 从 n-1 阶爬 1 步的方法数 + 从 n-2 阶爬 2 步的方法数。
  • 即：f(n) = f(n-1) + f(n-2)。

2. 动态规划的核心思想

(1) 定义状态

• dp[i]：表示爬到第 i 阶台阶的方法数。

(2) 状态转移方程

dp[i] = dp[i-1] + dp[i-2]

• 解释：
  • 从 i-1 阶爬 1 步到达 i 阶。
  • 从 i-2 阶爬 2 步到达 i 阶。

(3) 初始化

dp[0] = 1  // 初始状态（地面）
dp[1] = 1  // 第1阶只有1种方法（爬1步）
dp[2] = 2  // 第2阶有2种方法（1+1或直接2）

3. 代码实现与逐步解析

(1) 基础动态规划（空间复杂度 O(n)）

1
2
3
4
5
6
7
8
9
10

var climbStairs = function(n) {
    if (n <= 2) return n;
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1; // 初始状态
    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)（存储整个 dp 数组）

(2) 优化空间（空间复杂度 O(1)）

1
2
3
4
5
6
7
8

var climbStairs = function(n) {
    if (n <= 2) return n;
    let a = 1, b = 2; // a=dp[i-2], b=dp[i-1]
    for (let i = 3; i <= n; i++) {
        [a, b] = [b, a + b]; // 状态转移
    }
    return b;
};

• 优化原理：
  只需保存前两个状态（dp[i-1] 和 dp[i-2]），无需存储整个数组。

4. 为什么动态规划比递归更优？

• 递归的问题：
  计算 f(5) 时会重复计算 f(3) 和 f(4)，导致指数级复杂度。
• 动态规划的优势：
  通过递推公式 自底向上 计算，避免重复计算。

5. 分步示例（n=5）

• 最终结果：b = 8（即 f(5)=8）

6. 数学本质

• 斐波那契数列：1, 1, 2, 3, 5, 8, 13...
  • f(n) = f(n-1) + f(n-2)
  • 爬楼梯问题是斐波那契数列的变种（初始条件不同）。

7. 如何想到动态规划？

1. 识别重叠子问题：
   • 计算 f(5) 需要 f(4) 和 f(3)，而 f(4) 又需要 f(3) 和 f(2)，存在大量重复计算。
2. 定义状态：
   • 用 dp[i] 表示问题的子解。
3. 建立状态转移：
   • 通过问题规律（如 dp[i] = dp[i-1] + dp[i-2]）递推。

8. 边界条件处理

• n=0：返回 1（地面算一种方法）。
• n=1：返回 1（只有一种爬法）。
• n=2：返回 2（1+1 或直接 2）。

总结

• 动态规划适用场景：
  问题具有 最优子结构 和 重叠子问题 特性。
• 爬楼梯的关键：
  将大问题分解为小问题，通过递推公式避免重复计算。
• 优化核心：
  用有限变量代替数组，将空间复杂度从 O(n) 降至 O(1)。