Category: Sorting and Searching
-
Sum of Two Values
想法 – 1 用hash map, 也就是python的dict來記錄下位置，並在每一個迴圈都比較現在 x-i的值有沒有在li裡，有的話就輸出dicta對應的位置。 但是這種寫法會跑太多迴圈，超時。（ 因為 li 是個 list，in 判斷會是 O(n) 的操作。整體會退化成 O(n²)！）即使改成if s in d 也還是會超時！！ 改Ｃ＋＋ 並且在同個迴圈中加入map，避免「重複的數字」只保留到最後一個出現的位置，也減少迴圈運行的時間
-
Restaurant Customers
題目說測資會到10**9，接近好幾GB了，所以本篇介紹兩種寫法，如果測資小的話可以考慮用第一種寫法。 想法 – 1 差分, 前綴是啥可以參考這篇 : https://hackmd.io/@HyC-1029/By-o9OAoyg 想法是:透過差分來標記區間[a:b]內有人，然後再用前綴和將正確人數還原出來。 // 小心如果測資>10**6的話就會爆炸 想法 – 2 因為CSES的測茲有一個20,000，兩個迴圈來回就直接超時了(記憶體也爆掉)， 所以改是看看用C++線性搜。 一樣跟差分的想法，只要有人我就+1來計算進場人數，不過最後是一直比對 max()。 假設現在有一個input是 (1, 4)(2, 5)(7, 8) 我們用pair(a,x)將這筆資料存到vector中，a表時間，x表進場人數，會變 vector= {{1, +1}, // 1點來一人{2, +1},{4, -1}, // 4點走一人{5, -1},{7, +1},{8, -1}} 接著再透過累加的方式線性搜
-
Concert Tickets
用python容易超時，不超時的話要用外部額外排序list套件，但要用到外部套件就不是個好選擇了，所以這裡提供用python表示想法，會用C++來實作 想法 仔細想想就會發現這題比較沒辦法用雙指針(因為涉及刪除)。 所以這裡的想法是 ” 將顧客的預算插入到票價list中，取左邊那個 “ 這樣就能取到<=票價的最優價格了 bisect.bisect_right(s,t) 會回傳” c要插入s裡的最佳index “ 所以透過套件快速二分搜來達到快速找到該值右邊index C++ 透過multiset的upper_bound 來達到同樣效果，且multiset可以依值保持有序
-
Ferris Wheel
看到題目就知道要用貪心，因為我們要一直找體重最接近x的人來湊， 除非>x，否則ans+=1。 除了貪心，還可以用雙指標–頭尾往中間，但是為什麼? 假設現在有一個小到大排序好list，因為一個車廂可以載最多2人，所以我們可以考慮把 “最重(right)跟最輕(left)” 放在同一車廂，盡可能的在 right-left <= x 的情況下接近x。