GG 只寫出三題
https://i.imgur.com/5U04VCr.png
看討論區 真的要用線段樹喔
我想說雖然一眼就像線段樹
不過 LeetCode 應該不會真的出一定要線段樹的題目吧
就在那邊想有沒有其他解法
我線段樹這輩子應該寫不超過五次 :(
看來是要認真練個幾遍了
其他題好像也沒什麼好講的
第二題就排序完之後分三種 case:
[0, n - 3]
[1, n - 2]
[2, n - 1]
也可以不用排序找前三大跟前三小
不過反正夠用
第三題有幾個觀察：
1. 如果不存在 2^k, 則不可能造出 2^k
2. 如果可以造出 [1, 2^k - 1] 且存在 2^k
則可以造出 [1, 2^{k+1} - 1]
所以找到第一個不存在的 2^k 即可
有點不想發 因為最後一題沒寫出來 就感覺沒什麼好發的
不過還是姑且紀錄一下八
哀

第四題看到就準備放棄了 線段樹真的不會但好像有人用不是線段樹的做法欸 最頂那個python的

那是很容易想到的假解 如果最後還是過了會是LeetCode的問題

你是說lee用的那個bit_count是假解 怎麼說願聞其詳 是會TLE嗎?

可能也不一定算假解 不過這種作法複雜度還是O(n^2)我不確定python整數底下怎麼做的 如果是像bitset那樣那加速64倍的話 10^5 * 10^5 / 64就算過也會是在邊緣 而且我是不覺得應該過就是了你看lee也不是自己發一篇而是在別人底下留言

線段樹放棄

可能是吧 我對python不太熟 謝大師講解