力扣实战之移动零、盛最多的水、爬楼梯

本文是覃超老师的《算法训练营》的学习笔记

练题法则

5-10分钟读题与思考
- 不要纠结没有思路就直接看题解；
- 不要死磕觉得自己很失败，怎么我们就想不出来；
- 基本上这些算法题，让我们自己想出来是不可能的；
- 拿跳表的来说，如果我们能从0-1把它想出来，那我们就可以拿到图灵奖了；
- 所以记住！无思路就直接看题解，无思路就直接看题解，无思路就直接看题解！
- 我们只需要知道并且能运用即可！
有思路
- 自己开始写代码，没有，就马上看题解！
默写背题，熟练
- 做完题目后，我们需要记住这种题的思路和有N种解决办法；
- 重复再重复的默写，直到自己有深刻的影响；
最后开始自己写（闭卷）
- 到了这里如果我们还需要看别人代码，那就要回去背题；
- 能到达这个阶段基本这种题你已经开始熟悉的，接下来就是反复练习；

在哪里练题？

那肯定是力扣了！没有账号的小伙伴，马上就去注册个账号开始日复一日的练习吧！～

283题 - 移动零

283. 移动零｜难度：简单

题目讲解

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例：

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

这里需要注意的重点：

所有 0 移动到数组的末尾；
保持非零元素的相对顺序；
必须在原数组上操作，不能拷贝额外的数组；

解题思路

思考题解时，使用MECE原则 — 每一个思路都相对独立的思维，然后想到完全穷尽。首先不要管附加条件，先把有可能解决这个问题的思路都想出来，再评估哪一个办法是最优解。面试的时候也是一样，说出你所有可以想到的思路，然后分别讲出各自的优点与缺点，最后提出最优答案。

统计0的个数
- 循环数组找到0的位置，遇到0就为0的个数加一；
- 遇到不是0的时候，把非0的元素值与0的元素交换即可；
开新数组
- 给一个指针i从数组的头部开始递增；
- 给一个指针j从数组的尾部开始递减（也就是原数组的总长度）；
- 遇到零就往j指针的位置放，然后j--；
- 遇到非零就往i指针的位置放，然后i++；
- 缺点：内存使用会高；
- 不符合条件：必须在原数组上操作，所以可以实现但是不符合条件；
双指针交换
- 给两个指针i和j，并且默认都从0开始；
- i指向的是当前位置；
- j指针会一直移动，直到找到一个非零元素，然后与i位置的值交换；
- 如果j的位置与i不是一致的话，就可以给j的值换成0；
双指针替换后清零
- 这个与第三种方法一致，也是双指针；
- 唯一的区别是不在i指针扫描的时候替换零；
- 而是在替换完毕所有非零元素后，把剩余的全部位数都改为0；

解题代码

「方法一」 - 统计0的个数：

时间复杂度：$O(n)$ - N个元素就需要遍历N次
空间复杂度：$O(1)$ - 只对原数组进行替换操作

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
  let zeroCount = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] == 0) {
      zeroCount += 1;
    } else if (zeroCount > 0) {
      nums[i - zeroCount] = nums[i];
      nums[i] = 0;
    }
  }
};

「方法二」 - 双指针交换：

时间复杂度：$O(n)$ - N个元素就需要遍历N次
空间复杂度：$O(1)$ - 只对原数组进行替换操作

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
  let j = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      nums[j] = nums[i];
      if (j !== i) {
        nums[i] = 0;
      }
      j++;
    }
  }
};

「方法三」 - 双指针替换后清零：

时间复杂度：$O(n)$ - N个元素就需要遍历N次，加上最后清零是走了n减非零的个数，那就是O(n+n-i)，总的来说还是O(n)
空间复杂度：$O(1)$ - 只对原数组进行替换操作

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    var j = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            nums[j] = nums[i];
            j++;
        }
    }

    for (let k = j; k < nums.length; k++) {
        nums[k] = 0;
    }
};

边界测试用例

[0,1,0,3,12] [1,2] [0,0]

题解对比与分析

注意：以下数据都是在力扣中提交后返回的结果，每次提交都有可能不一致。所以相近的方案输出的结果有所差异也是正常的，最终最优方案要通过分析代码来确定，不能只以力扣输出的数据为准，只能供于我们作为参考。

方法

执行时间

内存消耗

「方法一」- 统计0的个数

96 ms（战胜17.82%）

37.1 MB

「方法二」- 双指针交换

72 ms（战胜87.23%）

37.2 MB

「方法三」- 双指针替换后清零

76 ms（战胜73.98%）

37.2 MB

分析一下：

第一种方法是通过统计0出现的次数来定位到需要替换0的所在位置，里面涉及一个i - zeroCount的运算，所以相对其他方法来说运行时间会更长一些；
第二个方法是通过两个指针一起运行，一个固定在0元素，一个一直走找到非0元素，最后做一个交换，这种方法没有涉及运算，同时也是一个循环就可以完成，相对来说是最优解；
第三种方法也是用了双指针，与第二种方法的唯一区别就是先替换掉所有0的元素，最后把剩余的元素全部一次性替换成0。可读性来说，个人觉得更容易懂，但是时间和空间复杂度和第二种方法是一致的。

11题 - 盛最多水的容器

283. 盛最多水的容器｜难度：中等

题目讲解

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例：

输入：[1,8,6,2,5,4,8,3,7] 输出：49

题目重点：

首先我们的目标是挑选两条柱子，从而让两个柱子之前可以得出最大的面积（面积越大自然可容纳的水就越多）；
挑选最长的两个柱子不等于拥有最大的面积，因为它们之间的距离也是决定空间的一个维度；
所以重点是找到高度和宽度比例最大的一对柱子，从而得出最大面积；
注意在运算面积时，我们只能用一对柱子中最短的一条作为高度，因为水只能填满到最短的那条柱子的高度；
面积运算公式： 高度 x 宽度 = 面积

解题思路

枚举 —— 暴力解法
- 遍历左边和右边，找出所有面积；
- 列出所有柱子的组合；
- 算出所有组合各自的面积；
- 最后输出最大的面积的一组；
- 缺点：遍历次数过高，所以时间复杂度会相对偏高
- 复杂度：时间复杂度 $O(n^2)$、空间复杂度 $O(1)$
双指针
- 左右两边都往中间移动；
- 需要移动左右两头的问题都可以考虑双指针；
- 相同情况下两遍距离越远越好；
- 区域受限于较短边的高度；
- 所以让较矮的那边的指针往内移动；
- 一直以上面的规则移动知道两个指针重合；

解题代码

「方法一」 - 枚举（暴力破解）：

时间复杂度：$O(n^2)$ - 双循环，所以总计循环了N^2。
空间复杂度：$O(1)$

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
  let max = 0
  for (let i = 0; i < height.length - 1; i++) {
    for (let j = i + 1; j < height.length; j++) {
      let area = (j - i) * Math.min(height[i], height[j])
      max = Math.max(max, area)
    }
  }
  return max
};

「方法二」 - 双指针：

时间复杂度：$O(n)$ - 双指针总计最多遍历整个数组一次。
空间复杂度：$O(1)$ - 只需要额外的常数级别的空间。

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let max = 0

    for (let i = 0, j = height.length - 1; i < j; ) {
        let minHeight = height[i] < height[j] ? height[i ++] : height[j --]
        let area = (j - i + 1) * minHeight
        max = Math.max(max, area)
    }

    return max
};

题解对比与分析

方法

执行时间（毫秒）

内存消耗

枚举（暴力破解）

984 ms （战胜9.99%）

35.9 MB

双指针

56 ms（战胜99.88%）

36 MB

分析一下

通过使用第二种方法，我们从$O(n^2)$的时间复杂度降到$O(n)$，总的执行时间大概是快了17倍。

70题 - 爬楼梯

283. 移动零｜难度：简单

题目讲解

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

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

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

示例 1：

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

示例 2：

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

题解重点

其实题目本身并不难，在力扣（LeetCode）是属于“简单”级别的题目，但是如果没有思路，或者对这个题目完全不了解的话，一点头绪都没有也是正常的，这种题目也就是属于套路题。如果我们是不知道的话，我们自然会难到不知道怎么做。我们要是知道了的话，那就变得相当容易了。

这里讲一下解题的思想：

首先我们解题时最大的误区是什么？
做题只做了一遍
至少要做五遍
然后我们优化的思想是什么？
空间换时间
升维思想（升级到二维）
看题时懵了怎么办？
首先我们能不能暴力破解？
最基本的情况我们应该怎么解决？能否化繁为简？
破解所有问题的法则：
找最近重复的子问题
为什么？因为写程序我们只能写if，else，for，while，recursion（递归）
计算机是人类发明的，计算机肯定是没有人脑那么强的，它其实就是一个简单的重复式机器
那么计算机运行的程序也是同理，它是用重复的东西来解决问题的
如果我们遇到算法题的时候，就是需要我们用程序去解决的问题，那问题的本身就是可重复的
无论是算法中的回述、分治、动态规划、递归等，全部都是在找重复性的原理
所以重点都是“找规律”

深度分析题目：

首先我们使用化繁为简的思维来分析：

要到达第一个台阶，我们只能爬1个台阶，所以只有一种方法的可能性，所以 n = 1 的时候，只有1种可能。

那如果我们要到达第二个台阶，我们要不就是连续爬2次1个跨度，要不就是一次性爬两个台阶到达第二个台阶。所以有2种可能性。

那如果是需要到达第三个台阶呢？

这里有个小技巧，要到达第三个台阶我们可以换一种思维去想，如果我们还是像第一个和第二个台阶的方式去列出可以到达第三个台阶的所有可能性，那如果n很大的时候，我们只靠人的大脑去想，那真的是太费劲了。但是这里有一个很巧妙的思维方式。
返过来想，我们想到达第三个台阶，只有两种可能可以到达：
要不就是从第二个台阶爬1个台阶到达
要不就是从第一个台阶爬2个台阶到达
那其实如果是第四个台阶是不是也是一样的？
要不就是从第三个台阶爬1个台阶到达
要不就是从第二个台阶爬2个台阶到达
这里就有一个规律了。要到达第n个台阶我们需要知道：
到达第n-1的台阶有多少种可能
到达第n-2的台阶有多少种可能
然后这两个相加就是到达第n的台阶有多少种可能

那其实这里就是老生常谈的斐波拉次数列:

$f(n) = f(n-1) + f(n-2)$

解题思路

斐波拉次（Fibonacci）- “傻递归“
- 直接使用递归循环使用斐波拉次公式即可
- 但是时间复杂度就很高 - $O(2^n)$
动态规划
- 用上面讲到的原理，到达第n个台阶只需要：爬上 $n-1$ 台阶的方式数 + 爬上 $n - 2$ 台阶的方法数 = 爬上第 $n$ 个台阶的方式数
- 所以得出的公式是 $dp[n] = dp[n-1] + dp[n-2]$
- 同时需要初始化： $dp[0]=1$ 和 $dp[1] = 1$
- 使用这种方式时间复杂度降到 $O(n)$
动态规划2 - 只记录最后3个的方法量
- 与上面的动态规划的方法一样，但是这里我们只记录最后3个的台阶的爬楼方法数
- 使用f1，f2，f3作为储存变量
- 默认 $f1 = 1$ 和 $f2 = 2$ 即可
通项公式（Binet's Formular ）
- 有观察数学规律的同学，或者数学比较好的同学，会发现本题是斐波那次数列，那么我们也可以用斐波那次的“通项公式”
- 公式是：$F_n = \frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n]$
- 时间复杂度：$O(logn)$

解题代码

「方法一」斐波那次

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

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n <= 2) return n
    return climbStairs(n-1) + climbStairs(n-2)
};

「方法二」动态规划

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

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const 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];
};

「方法三」动态规划2

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

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
    if (n <= 2) {
        return n
    }
    let f1 = 1, f2 = 2, f3
    for (let i = 3; i <= n; i++) {
        f3 = f1 + f2
        f1 = f2
        f2 = f3
    }
    return f3
};

「方法四」通项公式

时间复杂度：$O(logn)$
空间复杂度：$O(1)$

/**
 * @param {number} n
 * @return {number}
 */
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);
};

题解对比与分析

方法

执行时间（毫秒）

内存消耗

「方法一」斐波那次

超出时间限制

N/A

「方法二」动态规划

68 ms

32.4 MB

「方法三」动态规划2

53 ms

32.3 MB

「方法三」通项公式

67 ms

32.4 MB

分析一下

按照时间复杂度来说，应该“通项公式”是性能最优的，但是力扣的执行时间不是很靠谱，这一点我在上面也说到，就不多解释了。
所以最优解还是第三种方法“通项公式”
接着就是“动态规划2”，因为只储存了3个变量，第二种方法需要用到数组。在空间复杂度上就占了优势。
而最后输一下傻瓜式的斐波那次递归，这种方法还没有执行完就已经被淘汰了。时间复杂度过高。

练题法则

在哪里练题？

283题 - 移动零

题目讲解

解题思路

解题代码

边界测试用例

题解对比与分析

11题 - 盛最多水的容器

题目讲解

解题思路

解题代码

题解对比与分析

70题 - 爬楼梯

题目讲解

题解重点

深度分析题目：

解题思路

解题代码

题解对比与分析

推荐专栏