Re: [閒聊] 每日leetcode
看板Marginalman作者JerryChungYC (JerryChung)時間1年前 (2024/08/06 08:43)推噓1(1推 0噓 3→)留言4則, 3人參與討論串644/1548 (看更多)
https://leetcode.com/problems/minimum-number-of-pushes-to-type-word-ii
3016. Minimum Number of Pushes to Type Word II
給一個字串 word
電話按鍵映射小寫英文字母集合 透過按的次數獲得字母
如 2 映射 ['a', 'b', 'c'] 按 1 次得到 a 按 2 次得到 b 按 3 次得到 c
現在將按鍵 2~9 重新對應到不同字母集合 每個鍵可以映射到任意數量的字母
找出輸入字串所需的最少按鍵次數
注意 1, *, #, 0 不映射到任何字母
Example 1:
Input: word = "abcde"
Output: 5
Explanation: "a" ~ "e" 分別對應 key 2 ~ 6
合計 1 + 1 + 1 + 1 + 1 = 5
Example 2:
Input: word = "xyzxyzxyzxyz"
Output: 12
Explanation: "x" ~ "z" 分別對應 key 2 ~ 4
合計 1 * 4 + 1 * 4 + 1 * 4 = 12
如範例 2 的圖顯示 key 可以不對應到任何字母
Example 3:
Input: word = "aabbccddeeffgghhiiiiii"
Output: 24
Explanation: "a" ~ "g" 分別對應 key 2 ~ 8
"h" 對應 two pushes on key 9
"i" 對應 one push on key 9
合計 1 * 2 * 7 + 2 * 2 + 6 * 1 = 24
思路：獲得每個字母出現次數後排序由大到小
前8個放在 one push 9~16 放在 two pushes 依此類推 就能得到最少次數
Python Code:
class Solution:
def minimumPushes(self, word: str) -> int:
return sum(v * (i // 8) for i, (_, v) in enumerate(Counter(word).most_
common(), 8))
Counter(word): 取得每個字母的出現次數
most_common(n = int | None = None): 由大到小進行排序 沒給 n 則回傳所有內容
enumerate(iterable, start: int): 獲得當前 index 與值 這邊從 8 開始計算
v * (i // 8): v 為出現次數, i 為 index, i // 8 決定放在 one push or two pushes
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.251.52.67 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722905020.A.1CE.html
→
08/06 08:44,
1年前
, 1F
08/06 08:44, 1F
※ 編輯: JerryChungYC (60.251.52.67 臺灣), 08/06/2024 08:49:02
推
08/06 08:49,
1年前
, 2F
08/06 08:49, 2F
→
08/06 08:50,
1年前
, 3F
08/06 08:50, 3F
→
08/06 12:31,
1年前
, 4F
08/06 12:31, 4F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 644 之 1548 篇)：