力扣每日一题 2021/12

2021-12-01

2021年的最后一个月,原诸事顺利!

12/1 连续字符

难度 EASY

遍历统计一下就行。

12/2 相对名次

难度 EASY

用个map来排序就行。

12/3 K 次取反后最大化的数组和

难度 EASY

连着简单题。。贪心就行。先改负的,要是负的改完了依然有剩余,则改目前最小的数(最大负数或最小正数,就在当前指针附近)

12/4 赎金信

难度 EASY

用大小26的数组存放字母就行。

12/5 超级次方

难度 MEDI

用递归来计算,比如$a^123 = (a^{12})^{10} * a^3$

如果要加快速度可以用快速幂。

12/6 截断句子

难度 EASY

太简单了,直接抄的。

12/7 边界着色

难度 MEDI

看了好几个非官方题解才看懂题意。看懂后就比较简单了,可以bfs来做。遍历当前元素的四周,如果不能满足(在网格内且颜色相同),则说明当前元素是边界,否则(即在网格内且颜色相同,即属于连通分量的一部分)只要未访问过就加入队列。

12/8 三个无重叠子数组的最大和

难度 HARD

想了半天,把题目复杂化了。题解给的解答十分简洁:

  1. 统计单个子数组的最大和maxsum1十分简单,滑动窗口即可。记录出现maxsum1时的指针位置m1pos
  2. 在此基础上统计2个子数组的最大和maxsum12,滑动窗口时,比较maxsum12和maxsum1 + sum2的值,如果需要更新,记录出现maxsum12时的指针位置m12pos1为m1pos,m12pos2为当前指针位置 + k
  3. 在此基础上统计3个子数组的最大和maxsum12,滑动窗口时,比较maxsum123和maxsum12 + sum3的值,如果需要更新,记录返回值{m12pos1, m12pos2, 当前指针位置 + 2k}
12/9 有效的井字游戏

难度 MEDI

把每种情况都考虑进去就行。

12/10 最短补全词

难度 EASY

简单题。

12/11 在线选举

难度 MEDI

用哈希表来记录每个选举人有多少票。然后中一次循环中统计处每一个投票时刻的领先人,记录下来,这个人就是在times[i]到times[i+1]时间段(左合右开)的领先人。

这些工作都在初始化中,做完后每次查询时,只需要调用upper_bound,这个迭代器的前一个就是所要找的迭代器,计算得到pos,返回对应选举人。

12/12 转换成小写字母

难度 EASY

弱智题。

12/13 保持城市天际线

难度 MEDI

披着中等难度的简单题,统计横纵最大值即可。

12/14 课程表 III

难度 HARD

披着困难难度的中等题。一开始出于现实生活的惯性没有反应过来,这里的课程可以自己随便选择开课时间,只要能在lastday之前完成就行。那么,按照lastday排序,每次贪心选lastday最小的看能不能上,如果能直接加入队列,如果不能则看看把队列里当前最大的课程拿出来和当前的比较,如果当前的更小就替换(节省了一些时间)。

12/

难度 EASY

12/

难度 MEDI

12/

难度 HARD

本文阅读量: