LeetCode Weekly Contest 307题解报告
【 NO.1 赢得比赛需要的最少训练时长】
解题思路
能量值直接求和即可。经验值可以直接循环累加,然后判断。
代码展示
【NO.2最大回文数字】
解题思路
统计每种数字的数量后,优先选用最大的数字即可。
代码展示
【NO.3 感染二叉树需要的总时间】
解题思路
nextpr相当于求以 start 为根的树的深度。先 dfs 构图,再 dfs 求深度即可。
代码展示
【 NO.4 找出数组的第K大和】
解题思路
简化版:给定非负整数列表,求第 k 小和。给列表排序,然后用堆记录以 i 结尾的最小和 sum, 每次从堆中取出当前最小的 (sum, i), 然后放入 (sum + list[i + 1], i + 1) 和 (sum + list[i + 1] - list[i], i + 1)。第 k 次从堆中取出来的即第 k 小的子序列和。
将原数组分为负数和非负数两部分,将负数取反,得到两个非负数列表,然后求两个列表的前 k 小和。
最终问题就变成了从两个数组中各取一个数,求第 k 大和。可以类似地用堆解决,不过需要注意判重。
代码展示