Leetcode
力扣刷题 Day60 - 84
刷题最后一天，虽然中间有过几次打开拖延了，但还是坚持了下来，这两天再回顾下写一篇刷题总结。 单调栈第三天，对如何使用还是不够扎实，今天的题目也是想不出来直接看题解了。没看题解之前一点头绪也没有，看了题解之后又觉得原来这样就行，还是刷的题少。
84. 柱状图中最大的矩形
84…
力扣刷题 Day59 - 503.42
503. 下一个更大元素 II 503. 下一个更大元素 II - 力扣（Leetcode）
问题分析
几乎和「739. 每日温度」一样的一道题目，但却改成了循环数组，所以在第一次遍历完所有数组元素后，需要再从头（下标 0）遍历一次模拟循环…
力扣刷题 Day58 - 739.496
单调栈 单调栈实际上就是栈，只是在普通栈的基础上进一步要求每次入栈元素入栈后保持栈元素有序，若新元素入栈不合要求则将之前的元素出栈，直到符合要求再入栈，使之形成单调递增（只有比栈顶小的才能入栈）或单调递减的一个栈。
单调栈以时间换空间，时间复杂度为 \text{O}(n)。
一般…
力扣刷题 Day57 - 647.516
半个月的动态规划部分结束，不像这次刷题之前对动态规划一窍不通，但刷完也并没有说完全掌握了。有掌握定义 dp 数组、递推公式、初始化和遍历顺序、纸上模拟等等这些步骤如何实施，但每一步都还需要进一步加强，同时什么时候应用动态规划也还需要在不断刷题中明确。 647. 回文子串
647.…
力扣刷题 Day56 - 583.72
583. 两个字符串的删除操作 583. 两个字符串的删除操作 - 力扣（Leetcode）
问题分析
定义 dp[i][j]
dp[i][j] 表示对于字符串 word1 的 [0,i-1] 区间和字符串 word2 的 [0,j-1] 区间变为相同所需最小步数。
确定…
力扣刷题 Day55 - 392.115
392. 判断子序列 392. 判断子序列 - 力扣（Leetcode）
问题分析
若给定字符串 s 与 t 的最长公共子序列的长度与 s 一致，则说明 s 是 t 的子序列s 是 t 的子序列，从这个角度思考和「1143. 最长公共子序列」完全是一道题目，所以当 s[i - 1…
力扣刷题 Day53 - 1143.1035.53
1143. 最长公共子序列 1143. 最长公共子序列 - 力扣（Leetcode）
问题分析
借鉴「718. 最长重复子数组」定义 dp[i][j] 表示以 i-1 结尾的 text1 子串和以 j-1 结尾的 text2 子串的最大公共子序列长度。有了定义后先在纸上模拟…
力扣刷题 Day52 - 300.674.718
动态规划刷到现在，越来越能掌握去和在题目中去应用。定义 dp 数组、找状态转移方程、初始化、确定遍历顺序、打印 dp 数组 debug，这一整套操作下来，今天的三道题目都可以 AC 通过。 300. 最长递增子序列
300. 最长递增子序列 - 力扣（Leetcode）
问题分析…
力扣刷题 Day51 - 309.714
今天的两道题目都是「122. 买卖股票的最佳时机 II」基础上增加了情境设定，股票系列刷到此刻，有找到窍门的感觉，两道题目一遍 AC。 309. 最佳买卖股票时机含冷冻期
309. 最佳买卖股票时机含冷冻期 - 力扣（Leetcode）
问题分析
和「122. 买卖股票的最佳时机…
力扣刷题 Day50 - 123.188
今天的两道题目自己可以做出来，开始掌握通过二维 dp 数组的第二维来表示不同状态这种做法。今天第一道题目 debug 的过程也让我开始理解为什么动态规划中需要把 dp 数组打印出来 —— 当未能求得预期解时，打印出来可以直观地对比查找状态转移方程或初始化的错误点在哪里。 123.…
力扣刷题 Day49 - 121.122
五一 “给学生上两天课 + 熬夜追剧 + 沉迷《宝可梦：朱》” 后遗症 —— 脑袋转不动，几乎都是跟着题解的思路去照做。一刷之后二刷很有必要。 121. 买卖股票的最佳时机
121. 买卖股票的最佳时机 - 力扣（Leetcode）
问题分析
dp 数组的含义
对于某一天…
力扣刷题 Day48 - 198.213.337
打家劫舍系列，给定的数据从线性数据到环形数据再到树状数据，只有线性数据的 198 我还有点思路，后两道都是看题解才明白如何去分析思考。 198. 打家劫舍
198. 打家劫舍 - 力扣（Leetcode）
问题分析
一开始推导的状态转移方程是 dp[i] = max(dp[i -…
力扣刷题 Day46 - 139.多重背包
139. 单词拆分 139. 单词拆分 - 力扣（Leetcode）
问题分析
问题关键在于思考的角度从能否由字典单词组成转换为能否利用字典单词组成（装满）给定的字符串（背包）
布尔型 dp[i] 表示长度为 i 的字符串能否被字典单词组成
状态转移方程
dp[i] 的状态由它…
力扣刷题 Day45 - 70.322.279
搞明白昨天的 518. 零钱兑换 II 后以为对于完全背包非常理解了，但做题还是会有疑惑的地方，看来我还是想太简单😫 70. 爬楼梯
70. 爬楼梯 - 力扣（Leetcode）
问题分析
之前用单纯的动态规划做过一遍，这一次再从完全背包的角度去思考…
力扣刷题 Day44 - 518.377
今天的两道题目 518、377 都和「494. 目标和」非常相似，只不过变成了完全背包。 开始有点找到怎么把题目描述问题转换为背包问题的感觉，但今天两道题目的遍历循环顺序上还有点模糊，需要再思考下。
完全背包
3. 完全背包问题 - AcWing 题库
问题分析
完全背包与 01…
力扣刷题 Day43 - 416.1049.494.474
四道 01 背包的应用问题，关键在于如何把问题情境转换为 01 背包，在这点上还需要多做题去见识各种转换。 416. 分割等和子集
416. 分割等和子集 - 力扣（Leetcode）
问题分析
题目的关键在于将选取数字放入子集的过程看作选取物品放入背包的过程…
力扣刷题 Day42 - 01背包
2. 01 背包问题 - AcWing 题库 暴力枚举
二进制枚举
Copy
#include <cstdio>
using namespace std;
int weight[1005], value[1005], b[1005];
int main() {
int n,…
力扣刷题 Day41 - 343.96
今天一共两道题目，「343. 整数拆分」即使看了题解也还未能完全掌握如何通过分析推导来得到解这道题的思路，「96. 不同的二叉搜索树」则是前几周刚好给学生讲过，因此一遍就过。之前和高中老师沟通社团学生的培养，聊到要让学生多刷题才能让学生遇到不同的题目有思路…