[LeetCode] 2268. Minimum Number of Keypresses

You have a keypad with 9 buttons, numbered from 1 to 9, each mapped to lowercase English letters. You can choose which characters each button is matched to as long as:

• All 26 lowercase English letters are mapped to.
• Each character is mapped to by exactly 1 button.
• Each button maps to at most 3 characters.

To type the first character matched to a button, you press the button once. To type the second character, you press the button twice, and so on.

Given a string s, return the minimum number of keypresses needed to type s using your keypad.

Note that the characters mapped to by each button, and the order they are mapped in cannot be changed.

Example 1:

Input: s = "apple"
Output: 5
Explanation: One optimal way to setup your keypad is shown above.
Type 'a' by pressing button 1 once.
Type 'p' by pressing button 6 once.
Type 'p' by pressing button 6 once.
Type 'l' by pressing button 5 once.
Type 'e' by pressing button 3 once.
A total of 5 button presses are needed, so return 5.

Example 2:

Input: s = "abcdefghijkl"
Output: 15
Explanation: One optimal way to setup your keypad is shown above.
The letters 'a' to 'i' can each be typed by pressing a button once.
Type 'j' by pressing button 1 twice.
Type 'k' by pressing button 2 twice.
Type 'l' by pressing button 3 twice.
A total of 15 button presses are needed, so return 15.

Constraints:

• 1 <= s.length <= 105
• s consists of lowercase English letters.

最少按键次数。

题目给了一个字符串 s，请你设计一个带有九个按键的键盘，从而使得输入 s 的按键次数最少。键盘的形式参考例子。

思路是统计 + 排序，涉及贪心的思想。首先用一个长度为 26 的数组统计每个字母的出现次数。然后我们对这个数组逆向排序，这样最多的出现次数排在前面。此时我们开始把字母往号码上填，为了使按键次数更少，我们需要将出现次数最多的字母尽可能地安排在每个号码的第一个字母位上，这样第一轮我们就会处理 9 个字母；接着我们对出现次数排名 10 - 18 这九个字母分别填在 9 个号码的第二个字母位上；剩余的字母再依次填写到每个号码的第三个字母位上。对于第一个字母位上的字母，按键一次；对于第二个字母位上的字母，按键两次；对于第三个字母位上的字母，按键三次。

时间O(nlogn)

空间O(n)

Java实现

 1 class Solution {
 2     public int minimumKeypresses(String s) {
 3         Integer[] map = new Integer[26];
 4         // 没有fill就会报错
 5         Arrays.fill(map, 0);
 6         for (int i = 0; i < s.length(); i++) {
 7             map[s.charAt(i) - 'a']++;
 8         }
 9 
10         Arrays.sort(map, (a, b) -> Integer.compare(b, a));
11         int res = 0;
12         for (int i = 0; i < 26; i++) {
13             if (i < 9) {
14                 res += map[i];
15             } else if (i >= 9 && i < 18) {
16                 res += map[i] * 2;
17             } else {
18                 res += map[i] * 3;
19             }
20         }
21         return res;
22     }
23 }

LeetCode 题目总结