那肯定是力扣了!没有账号的小伙伴,马上就去注册个账号开始日复一日的练习吧!~
283. 移动零|难度:简单
给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
这里需要注意的重点:
0
移动到数组的末尾;思考题解时,使用MECE原则 — 每一个思路都相对独立的思维,然后想到完全穷尽。首先不要管附加条件,先把有可能解决这个问题的思路都想出来,再评估哪一个办法是最优解。面试的时候也是一样,说出你所有可以想到的思路,然后分别讲出各自的优点与缺点,最后提出最优答案。
i
从数组的头部开始递增;j
从数组的尾部开始递减(也就是原数组的总长度);j
指针的位置放,然后j--
;i
指针的位置放,然后i++
;i
和j
,并且默认都从0开始;i
指向的是当前位置;j
指针会一直移动,直到找到一个非零元素,然后与i
位置的值交换;j
的位置与i
不是一致的话,就可以给j
的值换成0;i
指针扫描的时候替换零;「方法一」 - 统计0的个数:
- N个元素就需要遍历N次
- 只对原数组进行替换操作
/**
* @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;
}
}
};
「方法二」 - 双指针交换:
- N个元素就需要遍历N次
- 只对原数组进行替换操作
/**
* @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++;
}
}
};
「方法三」 - 双指针替换后清零:
- N个元素就需要遍历N次,加上最后清零是走了n减非零的个数
,那就是O(n+n-i)
,总的来说还是O(n)
- 只对原数组进行替换操作
/**
* @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 |
分析一下:
i - zeroCount
的运算,所以相对其他方法来说运行时间会更长一些;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 宽度 = 面积
、空间复杂度
「方法一」 - 枚举(暴力破解):
- 双循环,所以总计循环了N^2。
/**
* @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
};
「方法二」 - 双指针:
- 双指针总计最多遍历整个数组一次。
- 只需要额外的常数级别的空间。
/**
* @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 |
分析一下
的时间复杂度降到
,总的执行时间大概是快了17倍。
283. 移动零|难度:简单
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
示例 1:
输入:2 输出:2 解释:有两种方法可以爬到楼顶。
示例 2:
输入:3 输出:3 解释:有三种方法可以爬到楼顶。
其实题目本身并不难,在力扣(LeetCode)是属于“简单”级别的题目,但是如果没有思路,或者对这个题目完全不了解的话,一点头绪都没有也是正常的,这种题目也就是属于套路题。如果我们是不知道的话,我们自然会难到不知道怎么做。我们要是知道了的话,那就变得相当容易了。
这里讲一下解题的思想:
首先我们解题时最大的误区是什么?
然后我们优化的思想是什么?
看题时懵了怎么办?
破解所有问题的法则:
if
,else
,for
,while
,recursion
(递归)首先我们使用化繁为简的思维来分析:
要到达第一个台阶,我们只能爬1个台阶,所以只有一种方法的可能性,所以 n = 1 的时候,只有1种可能。
那如果我们要到达第二个台阶,我们要不就是连续爬2次1个跨度,要不就是一次性爬两个台阶到达第二个台阶。所以有2种可能性。
那如果是需要到达第三个台阶呢?
这里有个小技巧,要到达第三个台阶我们可以换一种思维去想,如果我们还是像第一个和第二个台阶的方式去列出可以到达第三个台阶的所有可能性,那如果
n
很大的时候,我们只靠人的大脑去想,那真的是太费劲了。但是这里有一个很巧妙的思维方式。 返过来想,我们想到达第三个台阶,只有两种可能可以到达:
那其实如果是第四个台阶是不是也是一样的?
这里就有一个`规律`了。要到达第`n`个台阶我们需要知道:
n-1
的台阶有多少种可能n-2
的台阶有多少种可能n
的台阶有多少种可能那其实这里就是老生常谈的斐波拉次
数列:
n
个台阶只需要:爬上 台阶的方式数 + 爬上
台阶的方法数 = 爬上第
个台阶的方式数
和
f1
,f2
,f3
作为储存变量和
即可
「方法一」斐波那次
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
if (n <= 2) return n
return climbStairs(n-1) + climbStairs(n-2)
};
「方法二」动态规划
/**
* @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];
};
「方法四」通项公式
/**
* @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
};
「方法四」通项公式
/**
* @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 |
分析一下