[闲聊] LeetCode Weekly Contest 343

楼主: fxfxxxfxx (爱丽丝)   2023-04-30 12:00:46
昨天双周赛 40 名,今天 58 名,开心
https://i.imgur.com/AMyk2Le.png
其实排名我原本以为会更烂
因为我中间有写错方向重写
最后一题蛮可爱的
1. Determine the Winner of a Bowling Game
这在第一题中算是很麻烦的了
维护这个x2 buff 剩余的回合数
如果这回合打出 10 分就重置成两回合
否则就减一
2. First Completely Painted Row or Column
因为数字不会重复,所以可以维护
1) R, R[i] 代表这一横排被选过的次数
2) C, C[i] 代表这一直排被选过的次数
照 arr 顺序选,选到就把相应的 R 和 C 加一就好
满了就 return
3. Minimum Cost of a Path With Special Roads
关键的观察是,只有两种走法
a) 走特殊通道
b) 正常的走到终点或某个特殊通道的入口
所以只要维护出入口加上起终点的 graph 即可
|V| <= 402, |E| <= |V|^2
之后用 dijkstra 即可
4. Lexicographically Smallest Beautiful String
我们要让字串中不存在长度 >= 2 的回文
假如 s 存在回文 t,则 t 拔掉头尾还是回文
所以 s 不合法若且唯若存在长度是 2 或 3 的回文
也就是我们只要让所有长度是 2 或 3 的子字串都不是回文就好
而长度是 2 的子字串不是回文若且唯若两个字符不一样
长度是 3 的子字串不是回文若且唯若头尾两个字符不一样
也就是我们只需要让当下这个字符和前两个不一样即可
要找出最小的 beautiful string
只要找出从尾巴数回来第一个可以增加又保持合法的 index
后面就在保持合法的情况下 greedy 的取最小的那个字符就好
作者: PyTorch (屁眼火炬)   2023-04-30 12:02:00
大师
作者: JIWP (JIWP)   2023-04-30 12:03:00
大师
作者: Rushia (みけねこ的鼻屎)   2023-04-30 13:25:00
你好优秀
作者: pandix (面包屌)   2023-04-30 14:13:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com