LeetCode Weekly Contest 307题解报告

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 大和。可以类似地用堆解决,不过需要注意判重。

代码展示