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
想了半天,把题目复杂化了。题解给的解答十分简洁:
- 统计单个子数组的最大和maxsum1十分简单,滑动窗口即可。记录出现maxsum1时的指针位置m1pos
- 在此基础上统计2个子数组的最大和maxsum12,滑动窗口时,比较maxsum12和maxsum1 + sum2的值,如果需要更新,记录出现maxsum12时的指针位置m12pos1为m1pos,m12pos2为当前指针位置 + k
- 在此基础上统计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