Biweekly Contest 90
Weekly Contest 317
都这个礼拜的，就一起写
这两场都有进前千名
如果能保持的话感觉近期可以破两千分
不过我打比赛好像开始有蹭AC的趋势
就是平常写每日通常都会刁到optimal为止
但这几场比赛常常在时间压力下就随便写一个能过就好的解
有些甚至是我觉得不应该过的
不是一个好现象
题目有八题
90-1: Odd String Difference
照字面意思写就可以了，
而且 vector<int> 有 == 可以用，随便写
90-2: Words Within Two Edits of Dictionary
这题我写很烂= =
正常人的暴搜是 query 和 dictionary 之间两两看 hamming distance,
复杂度 O(qdn)，q 跟d 分别是 query 和 dictionary 的大小 n 是字串长度
我一开始是随机选两个字母改成随便的值看有没有在 dictionary 里
O(q n^2 k^2 + d), k 是字母个数=26，复杂度直接爆炸 TLE
后来我甚至还是想不到 hamming distance
改用 meet in the middle，把所有从 dictionary 改一个字母的存进一个 set
再用从 queries 改一个字母的去找有没有在 set 里
复杂度 O((q+d) nk)，幸好还是过了，不过这算蹭过去的
90-3: Destroy Sequential Targets
这题很简单，余数相同的会在同一组
挑最多人的那组里的最小值就可以了
90-4: Next Greater Element IV
第一反应是写两个 stack，觉得不太可能错结果传上去WA
没多想就把 stack 改成 map
过是过了但复杂度多一个 log
赛后仔细推演才发现从第一个搬到第二个 stack 的时候
不能直接把刚 pop 掉的 push 到第二个，顺序会乱掉
这题也是没写好
317-1: Average Value of Even Numbers That Are Divisible by Three
无聊，照字面意思写
317-2: Most Popular Video Creator
无聊，照字面意思写
317-3: Minimum Addition to Make Integer Beautiful
要想办法让各位数的总和小于 target
例如 467, 6:
4 + 6 + 7 = 17，但加到 500 的话 5 + 0 + 0 <= 6
要给出所要增加的最小值
12345 的候选人是 12350, 12400, 13000, 20000, 100000
照这个规则一个一个检查就可以了
复杂度 O(log^2 n)
317-4: Height of Binary Tree After Subtree Removal Queries
看赛后讨论 只要存同一层能往下的前两深的深度
不过我当下是想不到这个解法
我用 two-pass 扫了两次树
第一次存每个节点能往下的最大深度
第二次算出移除这个节点时的答案
方法是: 移除左边节点的答案会是
max(往右走的深度, 上一层往另一边走的深度, 上上一层....)
因为是 recursive, 之前往其他方向走的最大深度可以传下来
就只要再花 O(n) 就可以更新完
很多题复杂度都烂烂的
但 LeetCode 测资不是很刁难，所以还是压得进去