README.md

comments	difficulty	edit_url	tags
true	中等	https://github.com/doocs/leetcode/edit/main/solution/2200-2299/2268.Minimum%20Number%20of%20Keypresses/README.md	贪心 哈希表 字符串 计数 排序

2268. 最少按键次数 🔒

English Version

题目描述

你有一个 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 <= 105
• s 由小写英文字母组成

解法

方法一：计数 + 贪心

Python3

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

Java

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

C++

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

Go

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