- 博客(65)
- 收藏
- 关注
原创 代码随想录一刷总结
从了解到代码随想录到报名训练营中间间隔了好几个月,因为家里有小孩一直都抽不出时间,后来想着逼自己一把就报名了。以我之前的刷题经验,一般第一遍刷题都会忘记的很彻底,后续应该会继续二刷,将之前的题解补充完善,希望之后能尽快有个二刷总结。
2024-03-19 13:41:13 80
原创 代码随想录算法训练营day60 | 84.柱状图中最大的矩形
求以哪根柱子的高度得到的矩形最大。循环遍历每根柱子,然后向左遍历得到柱子左边第一个小于柱子高度的,向右遍历得到柱子右边第一个小于柱子高度的,两者之间的距离为矩形的宽度,当前柱子的高度为矩形的高度。建立在暴力解法之上,优化了求当前柱子左右两边第一个小于柱子高度的过程,其中利用了已经求解的数据,不再是暴力遍历,具体可以看代码。遇见比栈顶元素小的元素开始弹出,栈顶元素的高度为矩形的高度,(当前元素索引 - 栈第二个元素索引 - 1) 为矩形的宽度。同样有三种解法,暴力法,双指针法,单调栈法。
2024-03-14 13:41:13 217
原创 代码随想录算法训练营day59 | 503.下一个更大元素II、42. 接雨水
单调栈解法:与前面两种解法完全不同,是按行为方向进行计算,计算的时候只要找到当前柱子左右两边比当前柱子高的就行(之前的解法是需要找到最高的), 然后按照min(左边高的柱子,右边高的柱子) - 当前柱子的高度 得到高度,然后根据 右边高的柱子索引-左边高的柱子索引-1 得到宽度,高度*宽度 得到面积,面积在遍历中不断累积。注意遇到大元素的时候要看栈内的两个元素,如果只有一个元素则不能积累雨水,直接从栈内弹出即可。和每日温度思路单调栈一致,但是组成了环,需要遍历两次数组。可以改为在一次循环中遍历两次数组。
2024-03-13 16:21:40 179
原创 代码随想录算法训练营day58 | 739. 每日温度、496.下一个更大元素 I
使用单调栈方式,遇到当前元素比里面元素大的开始弹出记录结果,因为已经遇到温度更高的,遇到小的元素则直接存储,添加到栈内的元素一个比一个小。相比于每日温度,主要是先将子集数组遍历一遍,存储在map中,方便遍历nums2的时候直接找到对应值的下标,写入结果。
2024-03-13 13:53:09 107
原创 代码随想录算法训练营day57 | 647. 回文子串、516.最长回文子序列
(2)如果s[i]与s[j]不相同,说明s[i]和s[j]的同时加入并不能增加[i,j]区间回文子序列的长度,那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。那么dp[i][j]一定是取最大的,即:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);(1)如果s[i]与s[j]相同,那么dp[i][j] = dp[i + 1][j - 1] + 2。dp[i][j]:字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]
2024-03-11 16:47:15 221
原创 代码随想录算法训练营day55 | 583. 两个字符串的删除操作、72. 编辑距离
word2[j - 1]) 时取最小的,即:dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;因为 dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2,所以递推公式可简化为:dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);dp[i][0] :以下标i-1为结尾的字符串word1,和空字符串word2,最近编辑距离为dp[i][0]。
2024-03-11 11:37:28 494
原创 代码随想录算法训练营day54 | 392.判断子序列、115.不同的子序列
dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
2024-03-08 15:12:07 245
原创 代码随想录算法训练营day53 | 1143.最长公共子序列、1035.不相交的线、53. 最大子序和
如果text1[i - 1] 与 text2[j - 1]不相同,那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列,取最大的。如果text1[i - 1] 与 text2[j - 1]相同,那么找到了一个公共元素,所以dp[i][j] = dp[i - 1][j - 1] + 1;即:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
2024-03-07 11:33:10 279
原创 代码随想录算法训练营day52 | 300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
所以:if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 +1 的最大值。注:因为下一个状态是由左上方推出,因此也可以使用滚动数组来节约内存空间。为什么是i-1和j-1,而不是i和j?原因在于能够简化初始化的代码。
2024-03-06 16:44:27 179
原创 代码随想录算法训练营day51 | 309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费
那么dp[i][0] = max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);操作一:前一天就是持有股票状态(状态一),dp[i][0] = dp[i - 1][0]前一天是保持卖出股票的状态(状态二),dp[i - 1][1] - prices[i]即:dp[i][2] = dp[i - 1][0] + prices[i];dp[i][j],第i天状态为j,所剩的最多现金为dp[i][j]。操作一:前一天就是状态二。
2024-03-05 11:15:42 275
原创 代码随想录算法训练营day50 | 123.买卖股票的最佳时机III、188.买卖股票的最佳时机IV
需要注意:状态0可以省略,和前两次买卖股票的题目一样,可以看到dp[i][1]的递推公式的写法不一样。dp[i][j]中 i表示第i天,j为 [0 - 4] 五个状态,dp[i][j]表示第i天状态j所剩最大现金。使用二维数组 dp[i][j]:第i天的状态为j,所剩下的最大现金是dp[i][j]题目要求是至多有K笔交易,那么j的范围就定义为 2 * k + 1 就可以了。大家应该发现规律了吧 ,除了0以外,偶数就是卖出,奇数就是买入。dp[0][j]当j为奇数的时候都初始化为 -prices[0]
2024-03-04 14:49:08 287
原创 代码随想录算法训练营day48 | 121. 买卖股票的最佳时机、122.买卖股票的最佳时机II
确定递推公式:dp[i][0] = max(dp[i-1][0], dp[i-1][1]-price[i]) dp[i][1] = max(dp[i-1][1], dp[i-1][0]+price[i])贪心解法:从头开始遍历,一直寻找当前坐标之内的最小值,用当前坐标的值减去最小值。可以卖出多次,在递推公式有变化,其余没有变化。暴力解法:两个for循环。
2024-03-04 11:11:16 155
原创 代码随想录算法训练营day47 | 198.打家劫舍、213.打家劫舍II 、337.打家劫舍III
那么考虑不要尾元素和不要首元素两种情况,保证首尾不会连续被偷,其它和打家劫舍一致。
2024-03-01 14:09:38 178
原创 代码随想录算法训练营day46 | 139.单词拆分、多重背包了解
多重背包和01背包是非常像的,每件物品最多有Mi件可用,把Mi件摊开,其实就是一个01背包问题了。在代码中可以分摊到数组中,也可以在01背包循环中再加一个遍历。下面是C++多循环一重的代码。
2024-02-29 23:32:41 180
原创 代码随想录算法训练营day45 | 70. 爬楼梯 (进阶)、322. 零钱兑换、279.完全平方数
物品可以无限次使用,这是一个完全背包问题(决定背包的循环顺序),并且是求排列问题(决定内外层循环顺序),和377. 组合总和 Ⅳ几乎是一样的。如何和背包问题联系起来?每次可以爬1到m阶楼梯,1阶,2阶,.... m阶就是物品,楼顶就是背包。和上一题322. 零钱兑换思想一致,没有差别。
2024-02-29 09:22:36 252
原创 代码随想录算法训练营day44 | 完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ
第i件物品的重量是weight[i],得到的价值是value[i]。因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。只要保证下标j之前的dp[j]都是经过计算的就可以了。外层for循环遍历物品(钱币),内层for遍历背包(金钱总额)的情况,这种遍历顺序中dp[j]里计算的是组合数(无序)!01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了,一维dp数组的两个for循环先后循序一定是先遍历物品,再遍历背包容量。2. 确定递推公式:dp[j] += dp[j - coins[i]]
2024-02-28 14:11:10 415
原创 代码随想录算法训练营day43 | 1049. 最后一块石头的重量 II、494. 目标和、474.一和零
开始看题目的时候意识不到和[416. 分割等和子集]相像,看了题解后发现主要代码确实一样,并且也是分成两份,还得继续学习。确定dp数组以及下标的含义:dp[j]代表重量为j的背包,最多可以背的最大重量为dp[j]确定递推公式:dp[j] = max(dp[j], dp[j-stone[i]] + stone[i])dp数组如何初始化:石头的重量都大于0,整个数组初始化为0确定遍历顺序:外层循环物品,内层从大到小循环重量举例推导dp数组。
2024-02-27 22:00:00 265
原创 代码随想录算法训练营day40 | 343. 整数拆分、 96.不同的二叉搜索树
规律比较难找,需要画几棵树总结规律。用最原始未优化的动态规划方法做。
2024-02-26 10:24:38 100
原创 代码随想录算法训练营day39 | 62.不同路径、63. 不同路径 II
遇到障碍的时候dp赋值为0,要注意在初始化的时候,只要遇到障碍,后面的数值都置为0,因为不可能到达了。按照这种方法自己做出来了,有点进步。
2024-02-24 22:07:00 928
原创 代码随想录算法训练营day38 | 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯
动态规划,如果某一问题有很多重叠子问题,使用动态规划是最有效的。动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的。动态规划问题五步曲。
2024-02-24 21:18:49 262
原创 代码随想录算法训练营day37 | 738.单调递增的数字、 968.监控二叉树
暴力超时,需要找到规律,比如98结果为89,214结果为199,从后向前遍历,如果i-1位>i位,则i-1位减一,后面其他位都改为9。
2024-02-23 21:18:39 189
原创 代码随想录算法训练营day36 | 435. 无重叠区间、763.划分字母区间、56. 合并区间
先找到每个字符出现的最远距离,分割点为该分割字符串所有字符最大的最远距离。能自己做出来,有进步的。
2024-02-23 17:17:14 250
原创 代码随想录算法训练营day34 | 860.柠檬水找零、406.根据身高重建队列、452. 用最少数量的箭引爆气球
先按照气球开始坐标排序,然后根据气球的重叠右边界进行判断是否需要增加箭。完全没想出来,先根据身高进行排序,然后根据人数进行插入。定义的数组可以直接更改为两个变量,更加清晰直观。代码的技巧很强,多学习。
2024-02-23 15:19:51 109
原创 代码随想录算法训练营day33 | 1005.K次取反后最大化的数组和、134. 加油站、135. 分发糖果
还有一个要从全局进行考虑,总油量必须要大于等于总消耗,因为这样才能在判断起始站后,后续的油量是大于等于消耗的,才能满足条件。从i开始累加剩余油量curSum,一但curSum<0,则调到当前位置的下一个,因为从i开始到当前都不可能作为起始站了。
2024-02-23 13:45:02 130
原创 代码随想录算法训练营day32 | 122.买卖股票的最佳时机II 、55. 跳跃游戏、45.跳跃游戏II
python语言使用range的写法是错误的,因为python不支持动态修改for循环中变量,使用while循环代替。这道题目关键点在于:不用拘泥于每次究竟跳几步,而是看覆盖范围,覆盖范围内一定是可以跳过来的,不用管是怎么跳的。思路挺难想到的,代码却很简单。
2024-02-23 09:51:24 108
原创 代码随想录算法训练营day31 | 455.分发饼干、376. 摆动序列、53. 最大子序和
如果for循环的是胃口,当前的胃口大于饼干,不满足条件,此时的饼干是最大的,这个胃口以后不可能被满足,因此胃口继续往小的走,寻找可能被这个最大饼干满足的胃口。如果for循环的是饼干,当前的胃口大于饼干,不满足条件,则饼干会走到更小值,更不会满足条件,但实际是有更小胃口的可能被满足,因此出现错误。贪心算法没有固定的套路,手动模拟一下可以从局部最优推出整体最优,而且想不出反例,那就试一试贪心。如果当前值之和为负数,那么直接舍弃,因为负数会拉低后面的数。贪心的本质是选择每一阶段的局部最优,从而达到全局最优。
2024-02-22 10:35:46 207
原创 代码随想录算法训练营day29 | 491.递增子序列、46.全排列、47.全排列 II
树结构的层级遍历上需要去重,因此需要了解该层级上什么元素已经被使用了。不是排序之后的递增子序列,而是原序列的递增子序列。不需要startIndex,标记是否使用。需要先排序,然后从树结构的层级上去重。
2024-02-21 11:30:36 212
原创 代码随想录算法训练营day28 | 93.复原IP地址、78.子集、90.子集II
和C++不同,使用列表存储已经分割的数据,而不是直接操作字符串。为了使用这个列表搞了老久,主要问题出在,在判断终止条件的时候,path也需要回溯一下。和之前做的一样,树结构的层级遍历不能重复,纵向可以重复。子集问题是收集树的所有节点。
2024-02-20 22:42:13 177
原创 代码随想录算法训练营day27 | 39. 组合总和、40.组合总和II、131.分割回文串
树形结构的层级遍历上去除,纵向结构不用去重。未用动态规划优化是否为回文串的过程。切割的思路和组合是类似的。
2024-02-20 15:55:42 102
原创 代码随想录算法训练营day25 | 216.组合总和III、17.电话号码的字母组合
剪枝,并且优化了求和操作。未剪枝,和组合题目类似。没做出来,看题解学习。
2024-02-19 15:05:24 194
原创 代码随想录算法训练营day24 | 77. 组合
今天开始回溯回溯的模板。for循环是横向遍历,backtracking为纵向遍历。回溯法解决的问题都可以抽象为树形结构,树的宽度为集合的大小,树的深度为递归的深度。
2024-02-19 13:37:03 219
原创 代码随想录算法训练营day23 | 669. 修剪二叉搜索树 、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树
将二叉搜索树转化为累加树 可以先求整个树的和,然后中序遍历,逐渐减去节点的值。看了题解之后,发现可以使用反中序遍历,即右中左遍历,这样就可以只用遍历一次。使用递增数组构建平衡二叉搜索树,从数组的中间开始构建。修剪二叉搜索树,利用了二叉搜索树的性质。改进一下pre的初始值。
2024-02-19 10:13:46 158
原创 代码随想录算法训练营day22 | 235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点
二叉搜索树,如果p和q都小于当前节点,则继续搜索左子树;如果p和q都大于当前节点,则继续搜索右子树。如果p和q分别大于和小于当前节点,则当前节点为最近公共祖先。我在写代码时漏掉了左右的返回值,这样会导致递归后得到的节点传递不过来。递归法,有返回值,看完视频后各种情况都很清晰。
2024-02-18 16:14:27 194
原创 代码随想录算法训练营day21 | 530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数、 236. 二叉树的最近公共祖先
二叉搜索树按照中序遍历为递增序列,计算最小绝对差只需要计算相邻两个元素之间的差值,找出最小值。可以遍历二叉树,得到数组,然后计算;也可以在遍历的时候直接计算,和之前的验证二叉树是一个思路。中序遍历,计算频率的代码技巧需好好学习。
2024-02-06 15:25:40 118
原创 代码随想录算法训练营day20 | 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树
在这种做法的时候,可以先声明一个最小值,但是有可能树中存在这个最小值导致结果报错,优化的做法是将遍历的第一个元素赋值给声明的元素,然后逐渐比较。看了题解之后,和我写的好不一样,需要花时间研究一下,看了视频。优化的做法:在中序遍历的时候,直接比较遍历值是不是递增的。直接的做法:中序遍历得到数组,看看数组是不是递增。比之前利用中序和后序构建二叉树简单一些。递归法,直接利用root1。写的不够简洁,重新优化一次。不使用最小值的办法优化一次。
2024-02-04 11:37:25 269
原创 代码随想录算法训练营day18 | 513.找树左下角的值、112. 路径总和、106.从中序与后序遍历序列构造二叉树
后续 path 改变时, res 中的 path 对象也会随之改变,因此无法实现结果记录。正确做法为:list(path)或者path[:]以 Python 语言为例,记录路径时若直接执行 res.append(path) ,则是将此 path 对象加入了 res;精简版的代码是不要求判断当前节点是否存在才能迭代的,直接有判断为空则返回False。求出所有满足条件的路径,因为要遍历整棵树,找到所有路径,不需要返回值。层序遍历的模板,稍微更改一下即可。的,可以看看注释中出现的结果。找最底层、最左边的值。
2024-01-30 22:28:16 267
原创 代码随想录算法训练营day17 | 110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之和
如何能判断是左叶子?当前节点只能判断是否是叶子节点,左节点需要父节点才能判断,因此我们遍历父节点进行判断。看了题解之后,其实代码有点冗余,因为已经判断是否为空的情况了,可以直接遍历左右节点。当父节点有左节点,且左节点为叶子节点的时候统计和。递归法,求高度,后序遍历。
2024-01-29 14:08:03 131
原创 代码随想录算法训练营day16 | 104.二叉树的最大深度、111.二叉树的最小深度、222.完全二叉树的节点个数
本次全部使用递归的方式实现。
2024-01-25 23:17:59 168
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人