medium做多，hard做精，easy做稳

—3.28 洗澡时有感

Content

Graph

1. Dijkstra

   3.30 ~ 4.2

2. Topological Sort

   4.3 ~ 4.4

Common

1. Enumeration

   4.5

2. Binary Search

3. Segment Tree

String

1. Brute Force

2. KMP

DP

1. DP
2. Greedy

3.28

475. 供暖器

很像我字节二面的算法题

排序+二分遍历能过

3.29

1004.最大连续1的个数 III

2024.考试的最大困扰度

两道一样的滑动窗口

1697.检查边长度限制的路径是否存在

第一次理解 离线 和 在线 的说法

很巧妙的根据dis和limit排序

保证dis < limit的情况下只需要用uf判断连通性即可

1504. 统计全 1 子矩形

枚举理解了

单调栈不是很懂

1277. 统计全为 1 的正方形子矩阵

这题虽然跟上题很像，但是可以dp，简单很多

1727. 重新排列后的最大子矩阵

看上去跟前面两题很像，但思路其实感觉是84/85的思路

预处理算包括当前位置在内的上方连续的1，然后对每一行排序，遍历，顺便剪枝优化

2157. 字符串分组

一眼就能看出是并查集

但是比较难想到是二进制枚举，以及替换一个字母的表示

有一些细节没想明白

3.30

1606. 找到处理最多请求的服务器

几乎没有思路，最后只能想到可能用优先队列，然后还是不知道怎么做

维护两个pq，分别根据编号维护空闲服务器，根据结束时间维护工作中服务器

很巧妙的用了 i + (idx - i) % k 入队，并且这里还用到了python负数取模变成同余的非负数的性质，

别的语言应该是 i + ((idx - i) % k + k) % k

目的其实都是一样的，保证得到的是一个不小于 i 的且与 id 同余的数，从而能够保证当前轮次以及下一轮次能够按照服务器编号顺序接受请求

743. 网络延迟时间

比较经典的Dijkstra

矩阵枚举和优先队列两种写法

1368. 使网格图至少有一条有效路径的最小代价

虽然知道要用Dijkstra但是读完题根本想不到，看完题解才明白

实际上就是顺着箭头的weight=0，变换方向weight=1

明白这一点之后就是板子题了

另外学习了一种 0-1 广度优先搜索 ，核心就是双端队列

weight为0的从队首入队，为1从队尾入队

这样就保证从原点开始的距离单调增

（可以拓展到图中只有两种weighta, b，a!=b 的情况

写法其实和dij类似

2203. 得到要求路径的最小带权子图

周赛没写出来的题hhh

主要是思路，能想到枚举相交点就很好解决了

想到了就是板子题

1514. 概率最大的路径

权重变成概率

dij板子题

唯一有点坑就是python没有大顶堆，得用 heappush(q, -elem) 和 -heappop(q) 实现

1976. 到达目的地的方案数

一眼dij

但是求方案数不太会，学习了一下

求出最短路之后反推就行，记得用@cache优化

3.31

728. 自除数

暴力，没啥好说的

第一次拿到每月打卡勋章hhh

1786. 从第一个节点出发到最后一个节点的受限路径数

一开始题意没读懂，理解了半天

dij，然后反推，跟1976很像，只是反推的条件不同

882. 细分图中的可到达结点

自己思考做出来了hard，很开心哈哈

核心还是先dij算出最小距离（weight为cnt + 1），之后遍历边，根据边的两点分别判断，最后加上可达的点即可

787. K 站中转内最便宜的航班

套完dij之后就不知道该怎么做了，主要是k的限制，看题解学习了一下

dist[i] -> dist[i] [j] ，其实就是dp思想

之后相应改一改dist就可以了

1928. 规定时间内到达终点的最小花费

跟787其实一样

dist -> cost

k -> max_time

Dij + dp

4.1

Happy April Fool’s Day!

晚上才开始刷题hhh

954. 二倍数对数组

一开始想的排序+二分，另外维护一个记录，细节好像比较麻烦（其实是不会写二分

后面想到了pq+dict，思路很清楚，但是由于python处理堆比较麻烦，写了40多行，还好一次ac

看了一下题解，只能说方向是对的

直接维护dict（用Counter，然后从绝对值小的开始判断即可

看题解还可以用拓扑排序做，记个TODO，刷完dij来再做一次

1947. 最大兼容性评分和

毫无思路，看了题解之后做的，做完还是不知道tag里的dij哪来的

先预处理出每个学生对应每个老师的得分，

之后由于数据量不大，想到二进制枚举，0/1代表当前老师是否已经被选，

接着需要记录状态转移，即当前枚举bit下最大得分，所以用了dp数组，

而且需要当前位为1才能进状态转移，因为是根据这个位不为1的状态进行转移的

有个比较tricky的地方，转移的时候要知道当前学生编号为c-1，其实就是因为已经当前已经有c-1个导师被选中了，学生和导师是一一对应的

1879. 两个数组最小的异或值之和

和1947几乎完全一样，唯一不同是dp数组初始化，以及需要注意base case

预处理+ 二进制枚举+dp

4.2

420. 强密码检验器

模拟，想不出来，就看答案了

看了还是不太会hhh，先放一放吧

778. 水位上升的泳池中游泳

一开始看到tag，往dij方向想，没想出来

看到题解后用bfs+pq很简单做出来

1584. 连接所有点的最小费用

mst板子题

用kruskal怎么写都不对，一开始发现边没从j+1开始造，改了发现还是不对，麻了

prim过了

407. 接雨水 II

一开始的思路是模仿二维的，维护四个方向的最小值，取最小值减，但是没有想具体实现，感觉比较麻烦

其实思路是对的，实现用最小堆+visited

首先边上一圈肯定接不到雨水，预处理，记录已经visit并且入堆，

之后循环取堆中最小的进行四周遍历，能填就往里填，再入堆（注意入堆的是接过雨水之后的高度，可能不变也可能变高

双周赛a3道，最后一题拓展KMP板子，不会

4.3

周赛第一次AKhhh

744. 寻找比目标字母大的最小字母

模拟就行，还可以二分

210. 课程表 II

和207类似，拓扑排序，顺便记录一下就行

拓扑排序其实就是维护入度+bfs

802. 找到最终的安全状态

建立反图再拓扑排序即可

看题解学习了dfs+三色标记，维护一个记录节点颜色数组，分别代表状态为未访问，正在访问的栈中/在环上，已访问过且不在环上，

对每个点进行dfs即可

310. 最小高度树

一开始想的统计度，最小的作为根节点，发现不太行

看了题解，其实思路差不多，也是拓扑排序bfs的板子

维护degree表，双向的图，用队列bfs，度为1的入队

其实最后只可能剩下1/2个可能的根节点

1203. 项目管理

除了拓扑没什么思路，无从下手

看了题解，思路真的牛逼

双重拓扑排序，先根据组的关系排一次，得到组的顺序，再根据每一组内的项目进行排序

有几个比较tricky的地方：一是没有组的需要改成不同的组号，维护变量遍历改即可，

二是需要注意在不同组的时候，需要根据项目建图，而不是根据组建图，vice versa

其间任何一次拓扑排序后结果不正确（有环，都可以直接return空

1462. 课程表 IV

板子题，另外维护一个前置节点即可

注意python的set取交集用 |

看题解发现了用dfs + @cache，不得不说python的@cache真的赖皮

1591. 奇怪的打印机 II

完全没有思路

看了答案才知道为什么用拓扑排序

对每种颜色进行遍历，确定最大范围，在这个颜色范围内，不是这个颜色，说明在涂完这个颜色后，又新涂了当前颜色，

所以可以理解为一种先后关系，原来的颜色 -> 现在的颜色，所以可以建图，维护入度

题目中限定数字范围为<=60，所以开61的空间就好

之后就是板子题了

犯了个很sb的错误，找了半天bug，心态崩了

4.4

307. 区域和检索 - 数组可修改

树状数组/线段树 板子题

1632. 矩阵转换后的秩

真困难题

因为只考虑每行/列的相对关系，所以可以用拓扑排序

但是写到最后出了点问题，因为当行/列元素相同时需要保证该元素的最终值为相等元素的值中最大的那一个，想了一下只能想到并查集，感觉很麻烦，就看答案了

结果一看真是并查集

不想改了，cv

（看了一下是codeforces div1的c题原题

1857. 有向图中最大颜色值

困难的点在于记录颜色值，没什么思路

看了答案，其实开个数组记录就可以了（或者说是dp

dp[i] [j]：到i点为止，颜色j的最大值，然后在拓扑排序的过程中更新状态即可

2050. 并行课程 III

跟1857很像，拓扑+dp维护所需最大时间即可

2115. 从给定原材料中找到所有可以做出的菜

很早之前周赛的一道题目，当时还不怎么会写拓扑排序hhh

思路很简单，但是比较坑的一点就是ingredients里面可能在recipes和supplies都没出现过，我的处理是只加入度不加边

2157. 字符串分组

真困难题

3.29做过的题，当时没做完，又做了一下，应该是之前做过几道二进制枚举题目的原因，完全理解了解题思路

由于 只考虑s1和s2的集合 ，也就是说出现顺序无关，并且每个字母最多出现一次，所以可以用二进制位表示，

为了得到答案的分组数和最大个数，需要用 并查集 ，

那么删除/添加一个字母，分别对应异或当前位，由1变0和由0变1，

替换一个字母，实际上是删除一个字母，然后再次遍历，并且只能是添加一个字母，

其中可以维护一个set来快速判断是否存在于word，以及record记录words中对应的并查集parent

最后9秒多过了，差点TLE了，看来评论说python卡常是真的

2127. 参加会议的最多员工数

真困难题

pending一下，不太会

题解说是内向基环树

看了群主的视频，思路很清晰了，主要是分析部分：

分析可得，对于图的每一个连通部分，有两种情况：

1. 有环，且环上的点个数 >= 3

2. 有环，且环上的点个数 == 2

对于情况1，最大满足条件的个数只能为环上的个数，因为此时每个点的两边都已经定了

对于情况2，此时图的形状是两元环+每个顶点延伸的边，

此时最大满足条件个数可以加上其他连通部分的情况2下的点数总和，

因为对于情况2中的顶点，无论是二元环上的点还是延伸边上的点，都还有另一边空着，

所以拓扑排序时，为每个点维护变量记录向外延展的个数，

维护一个visited数组，排序完后visited[i] = False为环上点，再对每一个连通分量进行遍历，择优

剑指 Offer II 051. 节点之和最大的路径

做过的题还是不会做

果然纯靠理解做和靠刷题堆砌的结果还是有差距的，说到底还是我太菜了

后序遍历就可以了，注意更新res的值和返回的值不一样，更新的值可以是l+r+root.val，因为在同一条路径上，但返回只能返回最大值了

剑指 Offer II 052. 展平二叉搜索树

主要是一开始用一个dummy，然后维护一个pre

剑指 Offer II 053. 二叉搜索树中的中序后继

利用好二叉搜索树性质中序遍历就可以了

应该是简单题。。

4.5

762. 二进制表示中质数个计算置位

暴力就行

1625. 执行操作后字典序最小的字符串

以为有什么厉害的解法，结果居然就是枚举

先累加遍历，再轮转遍历（反过来也行，然后取最小

795. 区间子数组个数

题解的思路很精妙：

小于等于right的子数组数 - 小于等于left - 1的子数组数 = [left, right]的子数组数，

所以写个count函数计算小于等于k的子数组数就可以了

1737. 满足三条件之一需改变的最少字符数

太菜了，根本没思路，答案思路：

分别统计ab中每个字母出现次数，然后对i进行枚举，使得a中每个字母都小于等于i，b中每个字母都大于i，

这样分别对应情况1和2，

有个tricky的点，枚举中a是可以的，但z不行，因为字母不能大于z，

情况3通过枚举i，使得a，b每个字母都为i，需要的操作数也就是ab的长度和减去i在ab中分别出现的次数，

最后择优即可

2013. 检测正方形

用counter或者hashmap记录一下，每次枚举遍历就可了

35. 搜索插入位置

二分，水一题hhh

–600啦，暂时不想刷了hh–

4.8

1044. 最长重复子串

看群主视频，学到了二分的一个小技巧：

mid 可以写成 mid = left + (right - left) / 2 ，也可以写成mid = right - (right - left) / 2 ，两种可以通过取0取1的边界case选择，防止死循环

4.9

780. 到达终点

能想到是逆向思维，但没想到是直接用mod

用减法会超时

只要知道 tx > ty 时，直接 tx %= ty 就好了

907. 子数组的最小值之和

一开始想到很多种思路，也想到单调栈了，但没想到具体实现

其实和84题很像，维护一个单调增栈，当前遍历到的元素小于栈顶元素，说明栈顶元素作为最小值的区间已经确定，累加即可，

即该元素值 * 左区间长度 * 右区间长度

4.16

这一周都在忙公司的事还有学校的复习，完全没刷题，直接来双周赛了

前两题很快，因为真的很简单

万万没想到第三题卡住了，其实也是个很简单的题目，想复杂了

因为只有5个面额，每次取款从大到小遍历一下就好了

6063. 节点序列的最大得分

第四题确实不会，只能想到枚举点，但是由于是4个点所以需要枚举2次确定两个中心点，

5e4肯定超时的

赛后知道可以枚举边，中间边就能确定两个点了，

之后贪心的选择一下剩下两个点即可，这里可以用heap做，

整体答案也就20行左右，真的算挺简单的

第四题的确有一定难度，总共A了300来人，

其实前三题做的快一点，还是能拿到一个不错的名次的，

但是第三题卡了很久，还是说明刷题需要坚持

我也很多次都在想，我刷题到底是为了什么

如果说一开始是为了面试，其实刷到这个地步，常见的题型该见也都见过了，面试前只需要反复刷两三天，把前面的捡起来就基本上没问题了

但是我又看到身边非常多的大佬，要么动辄几千题，要么是竞赛选手，这的确给了我不小压力，我也想变得跟他们一样强

刷到现在，如果说我还有继续刷下去的动力的话，应该是来自于后者

实际上，我也的确能在刷题中收获快乐，这种快乐来自于自己觉得经过几道几十道的题目的磨练，的确掌握了某些知识，又或者是周赛里面拿到好一点的排名上分，这些都能让我感觉我的努力得到了回报

那么既然如此，为什么我还会有这样的想法呢，还会犹豫今天是否要刷题，最终还是以各种借口搪塞掉

哎，我也不知道

但最起码，AC之后的喜悦是真实的

4.17

周赛打完

补充了todo

4.23

晚上做了字节的模拟笔试，前三题都挺简单的，也记不得了，没啥好说的，

第四题暴力过了80，不太想继续看了，出来了知道是树状数组板子题，记录一下

大概题意：

给两个长度都为 N 的数组 height 和 value ，分别表示每个人的高度和每个人的价值（身高都不一样

求身高递增序列的最大价值

问了rb，由于需要维护区间最值和单点修改，所以想到树状数组，

写一下代码：

（先记个TODO

1
2

def solve(N, height, value):
  	

2141. 同时运行 N 台电脑的最长时间

没思路，由于看到tag是二分，卡在如何根据电池情况计算最长时间

其实有一个点是，如果时间是t，那么对于使用时间大于等于t的电池，只能给一个电脑用，因为t之后就结束了，

想到这一点就离结论更近了：

对于每一个电池，能提供的价值为min(电池容量，给定t)，

check函数就很好写了

4.24

lc 93 改编，非数字可以当作任意数字使用，比如 10a1a02b3 可以是101.110.233

当时思路是想让字母尽可能小（0），特殊情况是前导位就取1

记个TODO

4.29

1996. 游戏中弱角色的数量

两个维度，一开始想的攻击升序防御降序然后遍历，但是这样会出现重复计算

所以对攻击降序，防御升序，再维护一个之前防御的最大值，如果当前防御小于该值，则说明为弱角色（贪心

4.30

五一假期算开始了，这几天也有点时间刷题，不过应该不像清明那会从早刷到晚，大概率还是像以前那样上午+下午，感觉不错的话准备秋招期间也就还按着这个节奏和强度来

300. 最长递增子序列

354. 俄罗斯套娃信封问题

LIS问题，学习了nlogn的做法，核心思路是dp+二分，

dp定义和n^2的定义不同，dp[i]是长度为i+1的子序列的尾部的值，

因为这样才是有序的可以二分，

需要注意left=res的时候才更新res

354先根据一个升序再另一个降序就好了，之后对降序的维度计算LIS，

降序是为了同一维度满足严格大于

先刷一部分rollinghash + binarysearch tag的

2156. 查找给定哈希值的子串

算是rollinghash入门题了，但是不知道为什么一直超时

换成群主的写法，倒着+每一步都取mod过了

5.1

6053. 统计网格图中没有被保卫的格子数

比赛时候一直没有特别好的思路，

实际上就是个模拟题，根据guard四个方向，碰到下一个guard break掉优化就好了，这样能保证是O(mn)的复杂度

惨痛的教训

该暴力就暴力

像200这种数据量

暴力就完事了

2258. 逃离火灾

又是个比赛没思路的题

其实如果能想到二分时间就简单很多，

以火为起点多元bfs，维护每个点被烧到的最短时间，

check就行，注意check的时候维护visited，不然会超时

1305. 两棵二叉搜索树中的所有元素

还原数组+双指针就好了

5.2

1044. 最长重复子串

之前做过但是没a的题，再做一次，

由于测试数据比较妖，所以check两次，并且MOD和POWER随机生成，

MOD是[1e9+7, 1 « 32]，POWER是[26, 30]

即使这样还是有概率冲突，交了3次才过

5.3

687. 最长同值路径

后序+左右相等时更新两侧但只返回大的一侧即可

1648. 销售价值减少的颜色球

题目意思很简单，也很容易想到二分，但是不容易写好

tricky的点在于无法整除的情况下，是否要多拿一个补齐

提交了挺多次都没过，也第一次让我认识到做一题不一定要一次过，

后面找时间重写一下吧

记个TODO

5.4

1823. 找出游戏的获胜者

队列模拟/数学（约瑟夫环）

2049. 统计最高分的节点数目

之前做过的又不会了hhh

想到一点，父节点方向的节点数可以通过总节点数 - 左 - 右 - 当前节点数算出来就很简单了，

再注意下最小分数为1即可

1201. 丑数 III

暴力超时，想到二分，思路是对的，但是不知道容斥原理

知道了就很简单了，记录一下（以及求gcd和lcm）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def gcd(a, b):
  # 记住小的在后面就行了
	if b == 0: return a
  return gcd(b, a % b)
def lcm(a, b):
  return a * b // gcd(a, b)
  
# 容斥原理	
# [1, n] 中能被 a, b, c整除的数个数
	total = n // a + n // b + n // c - n // lcm(a, b) - n // lcm(a, c) - n // lcm(b, c) + n // lcm(a, b, c)

650了，也就是一个月大概只做了50题，相较于之前100题/月下降了一半，但是我感觉这样慢下来每一题多想想，是在付出的时间以及回报中得到一个比较好的平衡。高题量可能并不意味着高收获，质量是很重要的，其实任何事都是这个道理。

最近各方面的节奏慢慢找回来了，希望自己能保持下去。