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 測資不是很刁難，所以還是壓得進去