跳转至

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

解法

方法一：计数 + 贪心

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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
}

评论