Medium
Related Topics: Hash Table / String / Greedy / Sorting / Counting
LeetCode Source

解題想法

首先，我們計算出每個 char 出現的次數，並將此紀錄在 hash table 中

其中，key 是 char，value 是 char 出現的次數

之後我們將 hash table 以 value 的數值，將它從大排到小

最後我們開始計算出每個 key 出現的次數，從大到小

除了 "1" 和 "*" 和 "#" 以及 "0"

必定只會 push 一次，其他 char 是由以下方式計算

前 8 個會有最小的 push 次數，只要 push 一次

第 9 到 16 則需要 2 次

第 17 到 24 需要 3 次

第 25 到 26 需要 4 次

我們把出現次數 * push 次數做加總即是答案

Complexity

Time Complexity: O(nlogn)
Space Complexity: O(n)

Python

class Solution:
    def minimumPushes(self, word: str) -> int:
        d = {}

        for i in range(len(word)):
            if word[i] not in d:
                d[word[i]] = 1
            else:
                d[word[i]] += 1

        nd = dict(sorted(d.items(), key=lambda x: x[1], reverse=True))

        res, count = 0, 0
        bag = []

        for k, v in nd.items():
            if k != "1" or k != "*" or k != "#" or k != "0":
                count += 1
                if count <= 8:
                    res += 1 * v
                elif count > 8 and count <= 16:
                    res += 2 * v
                elif count > 16 and count <= 24:
                    res += 3 * v
                else:
                    res += 4 * v
            else:
                res += 1 * v

        return res

C++

在 c++ 中，我們一開始得出的 hash table d 會因為要排序

透過 vector 以 pair<char, int> 存在 nd 中

在排序的定義中使用 lambda 定義排序規則

在 C++ 中，[] 是用來定義 lambda 表達式的符號。

在 pair 中定義 a 和 b

我們需要將 a.second > b.second 回傳，以便將 hash table 依照 value 從大排到小

class Solution {
public:
    int minimumPushes(std::string word) {
        std::unordered_map<char, int> d;

        for (char c : word) {
            if (d.find(c) == d.end()) {
                d[c] = 1;
            } else {
                d[c] += 1;
            }
        }

        std::vector<std::pair<char, int>> nd(d.begin(), d.end());

        std::sort(nd.begin(), nd.end(), [](const std::pair<char, int>& a, const std::pair<char, int>& b) {
            return a.second > b.second;
        });

        int res = 0, count = 0;

        for (const auto& kv : nd) {
            char k = kv.first;
            int v = kv.second;

            if (k != '1' && k != '*' && k != '#' && k != '0') {
                count += 1;
                if (count <= 8) {
                    res += 1 * v;
                } else if (count > 8 && count <= 16) {
                    res += 2 * v;
                } else if (count > 16 && count <= 24) {
                    res += 3 * v;
                } else {
                    res += 4 * v;
                }
            } else {
                res += 1 * v;
            }
        }

        return res;
    }
};