Re: [閒聊] Leetcode
Biweekly Contest 90
簡單分享一下思路
1.建一個 dict 把轉出來的 list 當 key，原字串 append 進他的 value
python 沒辦法把 list 直接當 key 要先轉成 tuple <- 我竟然今天才知道可以這樣...
寫的時候用了很白癡的 hash function
最後看哪個 len(value) == 1 就好
2.看到 size 這麼小就直接暴力法了 O(n^3)
字和字比對的方法就是看 a[i] != b[i] 的數量有沒有大於 2
3.看 Example 1 的例子應該很容易能想到跟餘數有關
把 nums[i]%space 同樣的元素放在一堆 看哪一堆最多元素
也是用 dict 就能解決
4.先看 size 感覺會是 O(n) 或 O(nlog(n)) 的演算法
看 Example 1 的 output 就感覺可能會用到 monotonic stack
一次想出 second greater 的版本可能有點困難
可以先想要怎麼找出每個元素右邊比他大的第一個元素
如果 nums[i] < nums[i+1] 那 nums[i] 的答案就直接出來了
如果 nums[i] > nums[i+1] 那就代表 nums[i] 要先存起來等 看看後面有沒有人比他大
所以可以維護一個遞減的 stack 每次檢查 nums[i] 有沒有大於 stack[-1]
不停 pop 直到 stack[-1] > nums[i] 或是 stack 空了
最後再把 nums[i] append 到 stack 裡
這樣是 first greater 的版本
接下來就可以接著想怎麼改成 second greater 的版本
上面 stack pop 的時候有什麼意義 差不多就提示到這
懂的都懂 不懂的我也不好說太多 說了你也不懂
細細品吧
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.193.176 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1667079944.A.914.html
推
10/30 09:49,
3年前
, 1F
10/30 09:49, 1F
討論串 (同標題文章)
