🔗 🟡 3016. Minimum Number of Pushes to Type Word II 1534

tags: Weekly Contest 381 貪心(Greedy) 計數(Counting) 排序(Sorting) 字串(String) 雜湊表(Hash Table)

題意

給定一個只由小寫英文字母組成的字串 wordword。

手機鍵盤上編號為 22 到 99 的按鍵與不同的小寫英文字母集合對應，可以通過按這些按鍵來形成單詞。例如，按鍵 22 對應 ["a","b","c"]["a","b","c"]，我們需要按一次鍵來輸入 "a""a"，按兩次鍵來輸入 "b""b"，按三次鍵來輸入 "c""c"。

現在你可以將編號為 22 到 99 的按鍵重新映射到 不同 字母集合。一個按鍵可以映射到 任意數量 的字母，但每個字母只能映射到一個按鍵上。

返回在手機上輸入 wordword 所需的 最少 按鍵次數。

思路：貪心(Greedy) + 計數(Counting) + 排序(Sorting)

由於我們的目標是最小化按鍵次數，因此基於貪心思路，應該將出現頻率最高的字母分配到最容易按到的位置。由於總共有 88 個按鍵，因此出現頻率前 88 高的字母在重新編號後都只需要 11 次按鍵，第 99 到 1616 高的字母則需要 22 次按鍵，依此類推。

具體步驟如下：

  1. 首先，使用一個長度為 2626 的陣列或雜湊表 cntcnt 來記錄每個字母的出現次數，則對於每個字母 chch ，其出現次數為 cnt[ch]cnt[ch] 。
  2. 將 cntcnt 中的字母按照出現頻率從高到低排序。
  3. 按照排序後的順序，將字母依次分配到 88 個按鍵上。使得頻率最高的 88 個字母只需按一次，接下來的 88 個字母需要按兩次，依此類推。
  4. 根據每個字母的出現次數和需要按鍵的次數，計算總按鍵次數 ansans ，返回 ansans 即可。

複雜度分析

  • 時間複雜度：O(n+∣Σ∣log⁡∣Σ∣)O(n + |\Sigma| \log |\Sigma|)，其中 nn 是字串 wordword 的長度，∣Σ∣|\Sigma| 是字元集合的大小，本題中為 2626 。
  • 空間複雜度：O(∣Σ∣)O(|\Sigma|)。
1
2
3
4
5
6
7
8
9
10
class Solution:
    def minimumPushes(self, word: str) -> int:
        cnt = [0] * 26
        for ch in word:
            cnt[ord(ch) - ord('a')] += 1
        cnt.sort(reverse=True)
        ans = 0
        for i, x in enumerate(cnt):
            ans += x * (i // 8 + 1)
        return ans
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int minimumPushes(string word) {
        vector<int> cnt(26, 0);
        for (char ch : word) cnt[ch - 'a']++;
        sort(cnt.begin(), cnt.end(), greater<int>());
        int ans = 0;
        for (int i = 0; i < 26; i++) ans += cnt[i] * (i / 8 + 1);
        return ans;
    }
};

寫在最後

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant, colors, backlight, bright, soft lighting, dreamy atmosphere, orange tone, (1girl, solo), long hair, looking at viewer, gentle smile, bangs, black hair, brown eyes, standing, sleeveless, indoors, blunt bangs, bag, sleeveless dress, handbag, dress, (orange dress), in the library, library, bookshelves, warm light filtering through windows, cozy ambiance, soft shadows, detailed background, vintage decor, scattered books, wooden furniture