刷题交流|一位穷学生趁着七天的免费会员刷了几道会员hard题,这是他身体发生的变化
8121
2022.03.01
发布于 浙江

一位穷学生趁着七天的免费会员刷了几道会员hard题,这是他身体发生的变化

前段时间因为周赛崩了,leetcode送了7天的会员,本着勤俭节约的精神,我就想在这7天内把会员hard题都刷完。当然截至目前我也就刷了大概1/3左右,到今天为止有什么收获呢?
首先是正面的,学到了一些相对冷门的算法(相对力扣而言,可能在别的地方是常用的),对一些数据结构也更加熟悉(线段树和树状数组),对经典套路(如区间dp)的题目的掌握程度也增加了。
其次是负面的一些效果吧,当然这个肯定因人而异。对我自己而言,因为急于求成(毕竟会员就7天),刷题时心态越来越浮躁,基本上看一题没思路就跳下一题,很难静下心来去思考问题,也正是因此我决定歇几天,放慢刷题的节奏。这也正是我发起了这个讨论的原因,就是想以一种粗略的方式总结下刷过的题目,记录下刷每道题时的心路历程。刷题的记录如下所示:
刷题记录.png


1168.水资源分配优化
一开始考虑的是dp,发现很难找到正确的最优子结构,隐隐约约感觉是个最小生成树。看了下提示,说要把该问题抽象成图论问题,更加确定了方向。最后是通过给原图加边的方式来对原问题做一个等价,然后求MST。
774.最小化去加油站的最大距离
一眼就看出是个二分,不过这里犯了个低级错误,把初始区间求错了。
358.K距离间隔重排字符串
隐隐约约感觉是个贪心,但是没想到严格的证明,试了提交下直接过了。被K=0坑了一次特例。
296.最佳碰头地点
分横纵坐标考虑,排序+中位数。可能当年算hard,在今天的leetcode里肯定已经不算了。
1274.矩形内船只的数目
同样是一眼二分,当时还考虑了下四分跟二分的效率区别。其实每次只用在矩形里切一刀就够了,题解里都切了两刀(分成四份),感觉效率是一样的。但二分写起来更快。
1692.计算分配糖果的不同方式
看数据范围一眼DP,想了好几种递推方式,但要注意不能重复计数(因为袋子是一样的),因此只能考虑最后一个糖果和前面n-1个糖果的关系。
1548.图中最相似的路径
因为路径是可以重复经过同一个顶点的,因此符合最优子结构,无脑DP就完了。要注意同名的城市。
265.粉刷房子
数据范围+明显的最优子结构,一眼DP。O(nk^2)的方法几乎是显然的,O(nk)的方法需要动动脑,特别要考虑最优和次优和第三优cost都一样的时候会发生什么。
1842.下个由相同数字构成的回文串
本质上是找重排列里下一个比它大的字符串。找最后一个顺序项,再进行一个交换和排序就可。
1714.数组中特殊等间距元素的和
在leetcode上很少见的分块题目,适合分块算法入门者学习。思路十分自然。
1216.验证回文字符串
典型的区间dp题,着重考虑区间的第一项和最后一项。
1246.删除回文子数组
这道题乍一看是个区间dp,仔细一想又觉得不能用区间dp,最后看了一眼题解,明白了确实是个区间dp。为什么一开始觉得不是区间dp,是因为leetcode上另一题的误导,546.移除盒子,因为在序列中间删除会破坏区间结构,所以一开始我觉得不是区间dp。但回文串的性质保证了这种情况不会发生。
1601.最多可达成的换楼请求数目
求一个图里找一组环,不交且包含最多的顶点。数据范围已经提示了贪心行不通了,老老实实数位dp吧。
1231.分享巧克力
和774差不多,带最大最小的题目优先考虑二分。
683.K个关闭的灯泡
树状数组模板题,因为树状数组下标从1开始,query又(一般)是开区间查询,导致+1,-1之类的关系一直搞不清楚,不过后来我自己改了下模板,用了我自己习惯的写法。
727.最小窗口子序列
看到数据范围,猜到是O(ST)的dp,顺着这个思路写,用dp[i][j]表示S[0...i],T[0...j]的结果,推出递推关系式。再用预处理把递推中的一个for循环优化掉。
2143.Choose Numbers From Two Arrays in range
不太熟悉这种DP,看了题解,理解了很久才想明白。关键是把符合题意的区间看成nums1[...]-nums2[...]=0的情况,用dp[i]表示nums1[...]-nums2[...]=i的情况。这个拓展感觉不太熟悉,需要多练练。
2158.Amount of New Area Painted Each Day
线段树模板题。我对这种数据结构比较生疏,改了好久才改明白。有一个push_down函数的传递把下一层的tag被上一层的tag覆盖掉,当上一层的tag=0,下一层的tag=1时就寄了。

1924.安装栅栏
学习了Welzl算法,大概思想是不断往外扩一个现有的圆。具体细节没弄明白,等有一天想明白了再把这题写了。

2005.斐波那契的移除子树游戏
尼姆游戏?克朗原理??博弈论真是我的知识盲区,需要挑个时间系统学习。学完再把这题A了。


写在最后

这只是个人刷题的一点碎碎念,如果对您有帮助就再好不过了。话虽如此,我也更加明白,要想真正从题目中学习到什么,最好的方法就是直接去做,而不是看其他人写的什么心得体会。毕竟,每个人的技能点都不同,能从一道题中发掘什么,学习什么,也都是因人而异的。
祝愿大家都能在算法进步的路上越走越远!最后,欢迎交流讨论!

评论 (28)