e# Leetcode
26. 删除排序数组中的重复项
题意:
- 就地修改
- 要求空间占用 O(1),不能用中间数组
思路:
- 双指针覆写,慢指针在元素不重复时才移动
- 重点不是 nums 修改,而是输出 length。结合 length,可以作一次 slice,给出 nums
- 倒序遍历,当元素重复时,删除当前项
- 正序剪切,会影响 i。倒序减切掉一个元素,i--,不影响待处理元素(身后)
70. 爬楼梯
转化:到达前一步楼梯的方法数+前两步方法数
递归实现:
- 优点: 直接利用问题的递推关系,思路直观。
- 缺点: 时间复杂度是指数级的 O(2n)O(2^n)O(2n),因为存在大量的重复计算,效率较低,可能导致栈溢出。
带缓存的递归(动态规划):
- 优点: 通过记录每一步的结果,可以避免重复计算,将时间复杂度降到 O(n)O(n)O(n)。
- 缺点: 需要额外的空间来存储每一步的结果,空间复杂度是 O(n)O(n)O(n)。
空间优化的动态规划:
- 优点: 只需要两个变量来存储前两步的结果,可以将空间复杂度降到 O(1)O(1)O(1)。
- 缺点: 实现稍微复杂一些,但在大多数情况下是最优的解决方案。
动态规划记录每个子问题的解来避免重复计算,通常用于优化递归解决方案。
121. 买卖股票的最佳时机
题意:
- 价格不会为负
思路:
- 模拟抄底,记录到目前为止最低价
- 如果希望知道哪天买入和卖出,可用双指针,慢指针总是指向最小价格
注意点:
- 给
Math.max
方法传入太大的数组,会导致超时,解决技巧,遍历时更新最小值 - 从第 2 个价格开始才能计算价格差,初始化最小价格为第一个价格
3. 无重复字符的最长子串
思路:
- 滑动窗口,更新记录最大长度
- 用 Set 维护一个窗口,窗口右边界从 -1 开始
- 连续的重复字符,左边界需要持续移动(while)
拓展:包含所有字母的最小子串(代码量较大)
387. 字符串中的第一个唯一字符
思路:
- 暴力,O(n^2)
- 两次循环,时间 O(n)
- 由于 map 中没有存索引,第二次循环还是遍历原数组,以输出索引
88. 合并两个有序数组
思路:
- 双指针,倒序取较大值,当 nums2 取空时,结束。 case 要考虑全,如 p1 == -1 p2 == -1
896. 单调数列
思路:
- 一次遍历,否定判断,输出一个为真或全部为真 实战:需要特殊技巧,提示后可写出
LCP 06. 拿硬币
公式:f(x) = x / 2 + x % 2
680. 验证回文字符串 Ⅱ
依赖知识:如何判断回文,1. 反转 2. 双指针 3. 迭代
回文指针末尾,lr 相邻,或 l === r,后者只剩一个字母,满足回文,比不比较都行
贪心算法
215. 数组中的第K个最大元素
- sort 降序后,取第 k - 1 元素 O(nlogn)
209. 长度最小的子数组
滑动窗口
- 右边界移动,直到找到解
- 找到解,左边界移动
1143. 最长公共子序列
dp 使用二维数组记录结果
边界,一侧为空字串
dp 方程
js
if (a === b) {
table[row][col] = table[row - 1][col - 1] + 1;
} else {
table[row][col] = Math.max(table[row][col - 1], table[row - 1][col]);
}
关联题目:583. 两个字符串的删除操作
三数之和
- 暴力 O n^3
- 双指针 如何做到不重复(有序 + 有两个数字不重复,第三个数字一定不重复,不会出现 [1, 2],[2, 1],每个数字开头的解要穷举)
js
function threeSum(nums, target = 0) {
// let res = []
let res: number[][] = []
nums.sort((a, b) => a - b)
for (let i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue
let l = i + 1
let r = nums.length - 1
while(l < r) {
let other = target - nums[i]
let sum = nums[l] + nums[r]
if (sum > other) r--
if (sum < other) l++
if (sum === other) {
res.push([nums[i], nums[l], nums[r]])
if (l < r && nums[l + 1] === nums[l]) { // 下一个值与当前值相同时,多跳一步
l+=2
} else {
l++
}
}
}
}
return res
}
console.log(threeSum([-1, -2, 2, -2, 0, 4, 1]))
console.log(threeSum([0, 0, 0, 0]))