刷题笔记

本文用以记录在leetcode上的刷题思路，以作复习(重刷/刷类似题)之用

笔记仅记录思路，源码见：https://github.com/GentleCold/leetcode

参考：

• https://programmercarl.com
• https://leetcode.cn

#include <bits/stdc++.h>
using namespace std;

第一章 基础

数组

704 二分查找(2024-02-19)

time: O(log n), space: O(1)

• left，right --> mid
• compare mid and change left/right
• 终止条件？边界？

27 移除元素(2024-02-19)

time: O(n), space: O(1)

• 暴力双层循环
• 双指针，右指针挑到非target给左指针(全换了)
• 优化：左指针发现target后让右指针用非target替换(只针对target，target少时有帮助)

977 有序数组的平方(2024-02-19)

time: O(n), space: O(n) // store the ans vector

• 本质就是归并排序
• 头尾往中间逆序可以减少边界条件判断

209 长度最小的子数组(2024-02-19)

time: O(n), space: O(1)

• 滑动窗口，左指针去掉数字，右指针增加数字

59 螺旋矩阵II(2024-02-19)

time: O(n^2), space: O(1)

• 模拟法，类似贪吃蛇的移动

链表

203 移除链表元素(2024-02-20)

time: O(n), space: O(1)

• 注意内存管理和head条件即可
• 可以用dummyhead来优化head的条件判断

707 设计链表(2024-02-20)

• 自己实现一个单向链表/双向链表
• 谨防未定义行为

206 反转链表(2024-02-21)

time: O(n), space: O(1)

• 递归/迭代两种方式（迭代更好写

24 两两交换链表中的节点(2024-02-21)

time: O(n), space: O(1)

• dummyhead大法好

19 删除链表的倒数第N个结点(2024-02-21)

• 考虑一次遍历，栈/双指针法，后者的空间复杂度更低

160 相交链表(2024-02-21)

• 哈希记录扫描过的节点
• 双指针遍历(有点类似倒水问题，关键在于长度差距)

142 环形链表II(2024-02-21)

• 同样使用哈希记录节点
• 如果要O(1)空间，用快慢指针(一个走一步，一个走两步，如果有环肯定相遇，并且可以根据相遇处推出环入口)

哈希表

• 若限制了数据大小且大小不大时即可用数组作答
• 需要判断是否出现过、找数字等，用哈希记录

242 有效的字母异位词(2024-02-21)

349 两个数组的交集(2024-02-21)

202 快乐数(2024-02-22)

time: O(logn), space: O(1)

• 哈希记录找到循环。还要考虑无穷大的情况，不过这种不会发生
• 既然是查环结构，那自然可以用快慢指针(参见142)

1 两数之和(2024-02-22)

• 暴力枚举，无法双指针因为排序会打乱下标
• 如何降到线性复杂度？考虑如何快速获取需要的数
• 一次遍历就行了，注意同一个数字不能重复出现

454 四数相加II(2024-02-22)

• 根据之前的经验，当然是哈希，如果只哈希一组数据为O(n^3)，空间为O(n)
• 分组可以再减少一波复杂度O(n^2+n^2)，空间为O(n^2)

15 三数之和(2024-02-22)

• 不用哈希，因为去重麻烦
• 排序+双指针相对更高效，确定一个位置，再双指针确定，同时也要注意去重，三个指针的去重！

18 四数之和(2024-02-22)

• 类似于三数之和，上升一个时间复杂度，为O(n^3)
• 注意下溢出，用long解决

字符串

344 反转字符串(2024-02-25)

• use swap

151 反转字符串中的单词(2024-02-25)

• 需要O(1)空间
• 去除多余空格（双指针）->反转所有单词->反转单个单词
• 别随便在循环条件里用j++!

28 找出字符串中第一个匹配项的下标(2024-02-25)

time: O(n+m), space: O(m)

• KMP算法！
• 前缀/后缀/next数组！
• Great answer! https://www.zhihu.com/question/21923021/answer/281346746
• 注意j跑到0时的情况，i和j都增加(注意j为-1或j为0，前者即不匹配的情况)

459 重复的子字符串(2024-02-26)

• 暴力枚举子串(n^2)
• s+s再匹配s

栈与队列

• 在SGI STL中，栈和队列并不算容器，被归类为container adapter，底层使用deque，不提供迭代器，在内存中不连续分布

232. 用栈实现队列(2024-02-28)

• 双栈，倒来倒去（push不倒，pop倒出来）

225. 用队列实现栈(2024-02-28)

• 单队列，队列加到尾部

1047. 删除字符串中的所有相邻重复项(2024-02-28)

• 用栈的消消乐

150. 逆波兰表达式求值(2024-02-29)

• 后缀表达式：遇到数字就入栈，遇到运算符就取出两个数字运算
• 判断是否为数字时注意负数（也可以直接判断是否为运算符

239. 滑动窗口最大值(2024-02-29)

• 优先队列，时间为O(nlogn)，同时记录下标，将所有不在滑动窗口中的最大值弹出
• 单调队列，即队列中元素是单调的，线性复杂度(每个元素进入和弹出各一次)

347. 前K个高频元素(2024-02-29)

• 哈希记录次数+优先队列，O(nlogk) (可以用快排优化)

二叉树

• 满二叉树/完全二叉树/搜索二叉树/平衡二叉树
• 前序/中序/后序/层序遍历(递归/迭代)
• 树的度/高度/深度

102. 二叉树的层序遍历(2024-03-01)

• 队列（广度优先搜索
• 固定size

226. 翻转二叉树(2024-03-01)

• 前序/后序反转

101. 对称二叉树(2024-03-01)

• 递归比较，注意是轴对称

222. 完全二叉树的节点数(2024-03-01)

• 利用完全二叉树的性质
• 通过深度判断节点个数
• 通过二分查找和位运算判断（查找底层节点个数）

110. 平衡二叉树(2024-03-02)

• 注意要求是每个节点高度差都不超过1
• 使用自低向上的递归（后序）可以降低复杂度，返回-1表示false

257. 二叉树的所有路径(2024-03-03)

• 遍历+回溯

404. 左叶子之和(2024-03-05)

513. 找树左下角的值(2024-03-05)

112. 路径总和(2024-03-05)

• 注意只有到叶子节点才能算(没有孩子)

106. 从中序与后序遍历序列构造二叉树(2024-03-06)

• 中序的顺序是左/中/右
• 后序的顺序是左/右/中
• 我们根据后序遍历来切割中序遍历
• 后序遍历也要跟着切割
• 后序数组切割根据中序的大小切，因为两者的长度肯定一样
• 后序数组也需要记录开始和结束的位置

654. 最大二叉树(2024-03-06)

回溯算法

77. 组合(2024-03-07)

• 回溯！push了再pop
• 减枝！如果之后的数字不够就结束循环

216. 组合总和III(2024-03-09)

• 通过降序来去重
• 循环也可以剪枝（通过剩余选择数

17. 电话号码的字母组合(2024-03-14)

39. 组合总和(2024-03-14)

40. 组合总和II(2024-03-14)

• 要求去重，经过排序即可
• 如果是重复数字就跳了(放后面)

131. 分割回文串(2024-03-14)

• 回溯递归分割点
• 动态规划记录是否为回文

93. 复原IP地址(2024-03-15)

78. 子集(2024-03-15）

• 组合和分割问题是找叶子节点，子集问题是找所有节点

90. 子集II(2024-03-15)

• 排序去重

491. 非递减子序列(2024-03-18)

• 使用back获取vector最后的元素时要注意是否为空
• 注意[1,2,1,1]的情况

46. 全排列(2024-03-18)

• 数组位置记录优于哈希记录

47. 全排列II(2024-03-18)

• 排序去重/哈希表

332. 重新安排行程(2024-03-24)

• 构建哈希表，记录机场间行程（图的边）
• 回溯构造行程
• 按照字典序排: map/priority queue
• 终止条件为结果长度达到边的数量+1

51. N皇后(2024-03-25)

• 直接记录皇后的位置
• 只需要记录列/两个斜角的一半

37. 解数独(2024-03-25)

贪心算法

455. 分发饼干(2024-03-26)

• 小饼干喂小胃口/大饼干喂大胃口
• 排序

376. 摆动序列(2024-03-26)

• 统计变化次数即可

53. 最大子数组和(2024-04-01)

• 子数组，数组中连续的部分
• 如果累加是正数则代表有贡献，如果累加是负数则重算

122. 买卖股票的最佳时机II(2024-04-01)

• 类似于摆动序列，多了求和的过程

55. 跳跃游戏(2024-04-01)

45. 跳跃游戏II(2024-04-01)

• 题目保证了可以达到最后，只用考虑何时增加跳跃次数(到达覆盖末端)

1005. K次取反后最大化的数组和(2024-04-01)

• 排序即可

134. 加油站(2024-04-04)

• 计算每一站的差值，记录可能的起始位置

135. 分发糖果(2024-04-04)

• 从前向后/从后向前两遍遍历

860. 柠檬水找零(2024-04-05)

406. 根据身高重建队列(2024-04-05)

• 使用链表，插入效率高效

452. 用最少数量的箭引爆气球(2024-04-06)

435. 无重叠区间(2024-04-06)

763. 划分字母区间(2024-04-07)

• 先找到每个字母的最远位置，再进行划分

56. 合并区间(2024-04-07)

738. 单调递增的数字(2024-04-08)

• 可以直接变成字符串处理

968. 监控二叉树(2024-04-08)

• 后序遍历
• 叶子节点不放
• 用三种数字区别（放了摄像头、被监控、没被监控）
• 注意根节点没被覆盖的情况

动态规划

509. 斐波那契数(2024-04-09)

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

70. 爬楼梯(2024-04-09)

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

746. 使用最小花费爬楼梯(2024-04-09)

• dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

62. 不同路径(2024-04-11)

• 滚动数组优化DP空间复杂度
• 组合直接计算

63. 不同路径 II(2024-04-11)

343. 整数拆分(2024-04-11)

• dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
• 对i-j不拆分/拆分

96. 不同的二叉搜索树(2024-04-12)

• dp[i] += dp[j] * dp[i - 1 - j];

01背包问题

416. 分割等和子集(2024-04-13)

• 找到一个和为sum/2的子集

1049. 最后一块石头的重量 II(2024-04-13)

• 实际为分成尽量相等的两堆

494. 目标和(2024-04-13)

• 只考虑加法，选择加法有几种

474. 一和零(2024-04-14)

• 两维度的背包

518. 零钱兑换 II(2024-04-17)

• 完全背包
• 此题要求组合

377. 组合总和 IV(2024-04-17)

• 注意遍历顺序，此题要求排列

70. 爬楼梯进阶(2024-04-18)

322. 零钱兑换(2024-04-18)

279. 完全平方数(2024-04-19)

139. 单词拆分(2024-04-19)

• 将单词看作物品，字符串看成背包
• 注意int减去unsigned int

多重背包

198. 打家劫舍(2024-04-20)

• dp[i]表示到第i个房间的最大收益

213. 打家劫舍 II(2024-04-20)

• 为头尾分开考虑

337. 打家劫舍 III(2024-04-20)

• 树状DP
• 选or不选

121. 买卖股票的最佳时机(2024-04-21)

• 持有昨天/买今天
• 之前卖掉/今天卖掉

122. 买卖股票的最佳时机 II(2024-04-22)

• 可以在之前已卖的基础上再次购买

123. 买卖股票的最佳时机 III(2024-04-22)

• 一天共五个状态

188. 买卖股票的最佳时机 IV(2024-04-22)

• 一天共2k+1个状态

309. 最佳买卖股票时机含冷冻期(2024-04-22)

• 今天买要在前两天卖了（跳过冷冻期）的基础上

第二章 LeetCode HOT100

3 无重复字符的最长子串(2024-02-21)

time: O(n), space: O(x) // 需要记录字符种类

• 区分字串和子序列
• 滑动窗口，注意长度为1的情况
• 优化：用map记录字符出现位置(右指针发现的重复字符不一定是最开始的那个)