2268. 最少按键次数 🔒

题目描述

你有一个 9 键键盘，按键按 1 到 9 编号，每个按键对应着几个英文小写字母。你可以决定每个按键对应哪些英文字母，但要满足如下条件：

26 个英文小写字母必须全部映射到这 9 个按键上。
每个英文字母只能映射到恰好一个按键上。
每个按键最多对应 3 个英文字母。

如果想打出按键上的第一个字母，只需要按一次。如果想打出按键上的第二个字母，则需要按两次，依次类推。

给你一个字符串 s ，返回基于你设计的键盘打出 s 需要的最少按键次数。

注意：字母映射到每个按键上，映射的顺序无法进行更改。

示例 1 ：

输入：s = "apple"
输出：5
解释：上图所示为设置键盘的最佳方法之一。
按按键 1 一次输入 'a' 。
按按键 6 一次输入 'p' 。
按按键 6 一次输入 'p' 。
按按键 5 一次输入 'l' 。
按按键 3 一次输入 'e' 。
总共按按键 5 次，所以返回 5 。

示例 2 ：

输入：s = "abcdefghijkl"
输出：15
解释：上图所示为设置键盘的最佳方法之一。
字母 'a' 到 'i' 每个只需要按一次按键。
按按键 1 两次输入 'j' 。
按按键 2 两次输入 'k' 。
按按键 3 两次输入 'l' 。
总共按按键 15 次，所以返回 15 。

提示：

1 <= s.length <= 10⁵
s 由小写英文字母组成

解法

方法一：计数 + 贪心

我们首先统计字符串 $s$ 中每个字符出现的次数，记录在数组或者哈希表 $\textit{cnt}$ 中。

题目要求按键次数最少，那么出现最多的 $9$ 个字符应该对应按键 $1$ 到按键 $9$，出现次数第 $10$ 到第 $18$ 多的字符再次对应按键 $1$ 到按键 $9$，以此类推。

因此，我们可以将 $\textit{cnt}$ 中的值按照从大到小的顺序排序，然后按照 $1$ 到 $9$ 的顺序依次分配给按键，每次分配完 $9$ 个字符后，按键次数加 $1$。

Python3JavaC++GoTypeScript

class Solution:
    def minimumKeypresses(self, s: str) -> int:
        cnt = Counter(s)
        ans, k = 0, 1
        for i, x in enumerate(sorted(cnt.values(), reverse=True), 1):
            ans += k * x
            if i % 9 == 0:
                k += 1
        return ans

class Solution {
    public int minimumKeypresses(String s) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            ++cnt[s.charAt(i) - 'a'];
        }
        Arrays.sort(cnt);
        int ans = 0, k = 1;
        for (int i = 1; i <= 26; ++i) {
            ans += k * cnt[26 - i];
            if (i % 9 == 0) {
                ++k;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int minimumKeypresses(string s) {
        int cnt[26]{};
        for (char& c : s) {
            ++cnt[c - 'a'];
        }
        sort(begin(cnt), end(cnt), greater<int>());
        int ans = 0, k = 1;
        for (int i = 1; i <= 26; ++i) {
            ans += k * cnt[i - 1];
            if (i % 9 == 0) {
                ++k;
            }
        }
        return ans;
    }
};

func minimumKeypresses(s string) (ans int) {
    cnt := make([]int, 26)
    for _, c := range s {
        cnt[c-'a']++
    }
    sort.Ints(cnt)
    k := 1
    for i := 1; i <= 26; i++ {
        ans += k * cnt[26-i]
        if i%9 == 0 {
            k++
        }
    }
    return
}

function minimumKeypresses(s: string): number {
    const cnt: number[] = Array(26).fill(0);
    const a = 'a'.charCodeAt(0);
    for (const c of s) {
        ++cnt[c.charCodeAt(0) - a];
    }
    cnt.sort((a, b) => b - a);
    let [ans, k] = [0, 1];
    for (let i = 1; i <= 26; ++i) {
        ans += k * cnt[i - 1];
        if (i % 9 === 0) {
            ++k;
        }
    }
    return ans;
}

2268. 最少按键次数 🔒

题目描述

解法

方法一：计数 + 贪心

评论