[閒聊] 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