leetcode刷题总结
唠唠叨叨的刷题总结,不定期更新.
栈
[1673] 找出最具竞争力的子序列
和最大序列差不多，入栈之后检测新元素大小，否则
[232] 用栈实现队列
用两个栈进行模拟，pop的时候将暂存区中的数据pop到另一个栈中。
[42] 接雨水
想到了用栈，但是怎么用的递推逻辑没想出来。。其实一个栈维护数列然后递归消除。
[84] 柱状图中最大的矩形
我觉得比接雨水还难一点，最优解法需要设置一个哨兵，因为每次将大于当前值的数据出栈了，没有考虑到出栈后的元素和后续元素中存在着联系，亦或者说是当前的元素如果是整个数列的最小值，那么需要考虑到\(nums.size()*min\_value\)的情况，所以利用哨兵的机制去计算。
[85] 最大矩形
这题属实恶心,我一开始以为和最大正方形面积一样的求法,然后发现并不行...是84题的纵向扩展..
[32] 最长有效括号
本来我还想用回文串。。不过一看数据规模就知道gg。正确做法是用栈模拟，加哨兵可以更加保持规律。或者用计数器就无法知道什么时候分段比如 "()((())"，所以从两边进行遍历得到最大结果。
递归
[95] 不同的二叉搜索树 II
需要了解如何建树，递归构建不同的左子树和右子树然后合并。
[37] 解数独 吐了,模板题做了老半天,最后发现是
x和y有个地方写反了.
动态规划
[486] 预测赢家
dp记录当前选择下的相对分数.
[264] 丑数 II
想到了dp,但是没想到那样dp.每个数字都是2,3,5的倍数,循环乘上去放入dp数组,要注意放入时的大小,以及去除重复项.
[518] 零钱兑换 II
需要理解动态规划下的组合去重方法。
[474] 一和零
二维背包问题，从大到小更新dp数组是关键。
[89] 格雷编码
找规律，类似dp，实际上下一个数的编码的多余部分就是上一个编码的镜像后前缀加1
[740] 删除与获得点数
将问题转换为打家劫舍。
[1388] 3n 块披萨
打家劫舍的另外一种版本，核心都还是序列中非连续数的最大和。推导出3n中取数的实际可能情况即为 在3n的数列中取不相邻元素的最大和。 利用2维dp进行求解。
[873] 最长的斐波那契子序列的长度
设置2维dp，由于数列是强递增的因此可以利用坐标确定子序列的最后两个元素，然后利用二分或者字典找到有没有x1。\(dp[x2][x3]=dp[x1][x2]+1\)
[1027] 最长等差数列
用873一样的套路会超时，而且这个重复问题也非常头疼。以后遇到会重复的直接暴力开最大容量的dp把。
[813] 最大平均值和的分组
带状态的一维dp，\(dp[i][k]\)是第i个位置切第k刀。比如我们要分三组得到最大值，假设从\([0~i]\)是1,2组，从\([i~n]\)为第三组。 满足 \(mean([0~j])+mean([j~k])\)最大, 那么从\([0~j] [j~i]\)分别为1，2组，他们也满足\(mean([0~j])+mean([j~i])\)最大，那么就分解成子问题了，即我们每个位置的最大值是,切上一刀的位置到这一刀的位置的,两组和最大. 特殊情况： 对于切一刀的情况，永远都是均值。
[188] 买卖股票的最佳时机 IV
对于股票买卖问题，如果是限制次数的问法，那么就一个套路：
- 当前持有 最大收益
- 保持不变
- 上一次卖出后+今天买入
- 当前不持有 最大收益
- 保持不变
- 这次买入后+今天卖出
[309] 最佳买卖股票时机含冷冻期
和188一样的套路，但是因为包含冷冻期，实际上购买n次的纵向扩展，购买n次的时候用的是一个变量进行反复更新，这里需要将一个变量扩展为3天进行滚动更新。
[72] 编辑距离
\(dp[y][x]\) 表示 \(word1[:y]\) 修改为\(word2[:x]\) 的最大编辑距离。
- 修改: \(aa\rightarrow ab = a\rightarrow a
+ 1\)。
- \(dp[y][x]=dp[y-1][x-1]+1\);
- 添加: \(aa\rightarrow ab = a\rightarrow ab
+ 1\)。
- \(dp[y][x]=dp[y-1][x]+1\);
- 删除: \(aa\rightarrow ab = aa\rightarrow a
+ 1\)。
- \(dp[y][x]=dp[y][x-1]+1\);
- 当\(s1[y]==s2[x]\)时不需要操作
- 修改: \(aa\rightarrow ab = a\rightarrow a
+ 1\)。
数组
[9] 回文数 这题最好要想到可以部分翻转。
[992] K 个不同整数的子数组
求解最多K个不同数字组成的数组,通过累加的方式我们将[2,1]这种情况累积到结果中,最终我们只需要删除 [1],[2] 这些值就能获得恰好K个不同数字组成的数组个数.
- 假设 1:
ans + 1 = ans + [1]
- 假设 12:
ans + 2 = ans + [2] , [1,2]
- 假设 121:
ans + 3 = ans + [1] , [2,1] , [1,2,1]
- 假设 1:
[214] 最短回文串
这题利用kmp算法是极好的.kmp算法可以将找到前缀和后缀中的相同部分.对于一个回文串,我们将其分为两部分,把后面一部分反向之后就可以发现他的前缀和后缀从中心开始匹配:
abfda b adfba->adfba b adfba.对于一个半回文串
abadfba,我们找他最短的回文串,那么就是要找到他的重复部分: \[ \begin{aligned} &\mathbf{aba}dfba \\ abfd&\mathbf{aba} \\ &\downarrow \\ abfd&\mathbf{aba}dfba \end{aligned} \]那么我们现在有kmp算法可以算前缀和后缀中重复部分,那么我们把可能出现重复的部分分别安排到前缀和后缀开始执行kmp算法,利用kmp算法求解到
next数组,这时候next数组的最后一位恰巧指向翻转字符串的重复部分的起始位置,截断后加上原字符串即可: \[ \begin{aligned} &\mathbf{aba}dfba \\ abfd&\mathbf{aba} \\ &\downarrow \\ \mathbf{aba}dfba&\$abfd\mathbf{aba} \\ &\downarrow\ (kmp) \\ , a, b, a, d, f, b, a, &\$, a, b, f, d, a, b, a\\ -1, 0, 0, 1, 0, 0, 0, 1, &0, 1, 2, 0, 0, 1, 2, 3(\text{next数组})\\ &\downarrow\ (merge) \\ abfd &+\\ &\mathbf{aba}dfba\\ &\downarrow\ (merge) \\ abfd&\mathbf{aba}dfba \end{aligned} \]最后附上kmp中计算
next数组的一个巧妙实现,来自b站:int findMaxCommon(const string& pattern) {
int n = pattern.size();
vector<int> next(n + 1, 0);
for (int i = 0, j = next[0] = -1; i < n; next[++i] = ++j) {
while ((j != -1) and pattern[j] != pattern[i]) {
j = next[j];
}
}
return next[n];
}
并查集
[1489] 找到最小生成树里的关键边和伪关键边
利用kruskal算法找到最小生成树,然后根据题意暴力寻找.
[1319] 连通网络的操作次数
直接并查集,记录无法merge的次数,最终集合与次数比较一下即可.
[959] 由斜杠划分区域
一般想法是把每个区域划分四个格子，然后并查。巧妙的方法是为每个连接线进行并查，如果成环了，那么分割区域加1.
[128] 最长连续序列 将数组全部放到set中然后寻找
树
[114] 二叉树展开为链表
找到root左边的右边前驱，将root右边给右边前驱。递归的方法真的挺难想的。
[117] 填充每个节点的下一个右侧节点指针 II
难度不算高，需要注意先递归右侧，否则左侧无法连接到右侧。
[440] 字典序的第K小数字
这题真的有点难,需要想到字典树,然后对分情况对字典树的间隔元素数量进行统计,我就是半天都没想好怎么去统计间隔数量,下面的代码能很好的解决这个问题,我开始是考虑分层,第一层10个,第二层100个.但是下面的代码很巧妙直接分层加统计一步到位.太妙了.
int getsteps(long pre, long n) {
long cur = pre;
long next = pre + 1;
long step = 0;
while (cur <= n) {
step += min(next, n + 1) - cur;
cur *= 10;
next *= 10;
}
return step;
}
哈希表
链表
字符串
[424] 替换后的最长重复字符
这种类型用滑动窗口，我做过一次第二次还是一直出错。写的时候需要注意滑动窗口自带剪枝的功能，对于右侧只需要一直扩展即可，左侧看时机进行收缩，并不需要收缩到特定长度，因为小于当前窗体长度的解被剪枝了。
[76] 最小覆盖子串 滑动窗口模板题,算是较为简单的hard了.
贪心
[763] 划分字母区间
每一步都更新当前区间的最大范围,直到最大范围就截取
[621] 任务调度器
通过贪心构造结果的公式，直接计算。否则需要进行模拟。
[45] 跳跃游戏 II
我觉得应该算动态规划的优化版，动态规划超时思考了一番我才写出贪心。
[376] 摆动序列
用两个状态的dp，或者用贪心去找峰值，如果找到峰值就更新。
[406] 根据身高重建队列
又是做过一次还是没想出来，按身高从大到小，排列从小到大排序。然后根据排序进行插入就能构建成功。我觉得重点在于身高高的人插入时不需要考虑身高低的，亦或者说每个人的排列去除矮的人后即按位排序。
二分查找
[153] 寻找旋转排序数组中的最小值
简单二分,比较mid和right的大小调整区间即可.
[81] 搜索旋转排序数组 II
不简单二分，太考验细节，首先需要加上\(left=n[left]==n[mid]?left++:left\)消除重复项，并且如果数组全部重复，时间复杂度为\(O(n)\)。接下来判断前面部分有序还是后面部分有序，再判断target是不是在有序部分。
[35] 搜索插入位置 二分的模板用这个比较好,最后结果的l位置是第一个不小于target值的位置,可以理解为以target的下界.
int l = 0, r = nums.size(), mid;
while (l < r) {
mid = (l + r) / 2;
if (target == nums[mid]) {
return mid;
} else if (target < nums[mid]) {
r = mid;
} else if (target > nums[mid]) {
l = mid + 1;
}
}
return l;
概率论
[470] 用 Rand7() 实现 Rand10()
- 需要理解\(Rand7()+7*(Rand7()-1)\)可以实现在\([1\sim49]\)中随机采样，那么我们可以从\(40\%10+1\)得到\([1\sim10]\)的随机采样。
- 取巧方法是\(Rand7()-1\)生成奇数偶数，\(Rand7()<6\)生成\([1\sim5]\)，然后根据\(\frac{1}{2}\times\frac{1}{5}\)得到\(\frac{1}{5}\)
BFS
[1631] 最小体力消耗路径
这题看起来像dp，其实不能直接dp。做法有很多，可以并查集、二分+dfs。我觉得dp+bfs的方法比较好。
数字
[231] 2的幂
方法有两种，方法一 : \((2<<30 \% n) ==0\)，因为2的幂次的倍数都是最大幂次的因子，因此肯定为0。 方法二：\((n \& -n) == n\) ， 在计算机里面 \(-n = ~n + 1\)，且\(n \& -n\)得到结果是\(n\)的二进制表示中最靠右的第一个1。那如果他只有一个1构成，就必然等于自身。
[326] 3的幂
可以连续除3进行判断。或者利用\(\log_3 \text{MAX_INT}\)找到最大的3的幂次，然后利用2的幂的方法进行计算。
[342] 4的幂
这题就不好用上面的方法了，因为4的因子有2。但4也是2的倍数，通过\((n \& -n) == n\)加上\(n\%3==1\)的条件可以进行判断。
还有一个常用技巧是\(n \& (n-1)==0\)， \(n-1\)可以将最右边第一个1置零，后序设置为1，可以用来快速找到第一个1的位置或者判断是不是只有一个1. 或者利用 \(n \&= (n-1)\)来消除1，可以统计1出现的次数(比循环右移更快)。
[260] 只出现一次的数字 III
用异或找到两个不同数字的异或结果，然后利用\(n \& (n-1)\)找到他们第一个不同的位，根据这mask将数组分为两组进行单独异或。
[201] 数字范围按位与
找到两个数的公共前缀即可。
[477] 汉明距离总和
我们直接统计每一个位上面的差异个数，那么每个位的汉明距离为\(k*(n-k)\)，累加即可。
[421] 数组中两个数的最大异或值
字典树+dfs
