[闲聊] LeetCode Weekly Contest 335

楼主: fxfxxxfxx (爱丽丝)   2023-03-05 12:00:23
这场不太好
https://i.imgur.com/3QkQbHP.png
今天恍神晚了 30 秒入场,不过应该影响不大
倒是第三题有点出乎我意料
1. Pass the Pillow
因为 time <= 1000 所以可以直接一步一步模拟
设定初始方向 dir = 1,当要超界时掉头 dir = -dir 即可
2. Kth Largest Sum in a Binary Tree
DFS/BFS 随便选,反正纪录每一层的和就好
之后取第 k 大的
我直接 sort 完取 index k - 1
反正 O(nlogn) 就绰绰有余不需要 O(n)
3. Split the Array to Make Coprime Products
这题有点出乎意料
我还真想不到不需要因式分解的做法
难不成 python 硬乘会过吗
我想了两个方法
第一个是同时纪录左边和右边因式分解,看有没有重复
每次移动边界只需要看当下被改动的地方有没有影响即可
因为每个数最多有 O(log n) 个质因子(可以压更紧)
但因为我的因式分解是用 map 存
所以总复杂度 O(nlog^2(n) + KlogK)
K 是 max(nums[i]) 用来预先计算每个数的质因子的
第二种方法是对于每一个质因子 p
都找出最早出现及最晚出现的 index: [left, right]
则 left 和 right 一定要在同一边
所以一要选就要选整个 range
总共最多有 O(min(nlogn, K/logK)) 个质因子
最后 sort 之后 greedy 的取相交的 range 即可
(和昨天的题目一样)
复杂度是对每个数做质因子分解的 O(nlogn)
以及预先计算的 O(KlogK)
4. Number of Ways to Earn Points
可以取好几个的背包问题
给的范围不需要任何优化直接硬暴就可以了
DP[i][v] = DP[i-1][v] + sum_{0<j<=count_i}(DP[i-1][v-j*mark[i]])
作者: a9486l (a9486l)   2023-03-05 12:01:00
大师.....

Links booklink

Contact Us: admin [ a t ] ucptt.com