Re: [閒聊] 每日leetcode
看板Marginalman作者sustainer123 (caster )時間1年前 (2024/08/06 09:39)推噓1(1推 0噓 2→)留言3則, 3人參與討論串647/1548 (看更多)
※ 引述《JerryChungYC (JerryChung)》之銘言：
: 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
思路:
記出現次數 排序 乘起來
不過我寫得有夠醜 哀
Python Code:
class Solution:
def minimumPushes(self, word: str) -> int:
record = defaultdict(int)
for c in word:
record[c] += 1
times = [v for v in record.values()]
times.sort(reverse = True)
count = 0
result = 0
for t in times:
if count < 8:
result += 1*t
elif count < 16:
result += 2*t
elif count <24:
result += 3*t
else:
result += 4*t
count += 1
return result
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.160.111 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722908373.A.783.html
推
08/06 09:43,
1年前
, 1F
08/06 09:43, 1F
→
08/06 09:43,
1年前
, 2F
08/06 09:43, 2F
→
08/06 09:46,
1年前
, 3F
08/06 09:46, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 647 之 1548 篇)：