输入单词需要的最少按键次数 II

100192. 输入单词需要的最少按键次数 II

给你一个字符串 word，由不同小写英文字母组成。

电话键盘上的按键与不同小写英文字母集合相映射，可以通过按压按键来组成单词。例如，按键 2 对应 ["a","b","c"]，我们需要按一次键来输入 "a"，按两次键来输入 "b"，按三次键来输入 "c"。

现在允许你将编号为 2 到 9 的按键重新映射到不同字母集合。每个按键可以映射到 任意数量 的字母，但每个字母必须恰好映射到一个按键上。你需要找到输入字符串 word 所需的最少按键次数。

返回重新映射按键后输入 word 所需的最少按键次数。

下面给出了一种电话键盘上字母到按键的映射作为示例。注意 1，*，# 和 0 不对应任何字母。

示例 1：

输入：word = "abcde"
输出：5
解释：图片中给出的重新映射方案的输入成本最小。
"a" -> 在按键 2 上按一次
"b" -> 在按键 3 上按一次
"c" -> 在按键 4 上按一次
"d" -> 在按键 5 上按一次
"e" -> 在按键 6 上按一次
总成本为 1 + 1 + 1 + 1 + 1 = 5 。
可以证明不存在其他成本更低的映射方案。

示例 2：

输入：word = "xyzxyzxyzxyz"
输出：12
解释：图片中给出的重新映射方案的输入成本最小。
"x" -> 在按键 2 上按一次
"y" -> 在按键 3 上按一次
"z" -> 在按键 4 上按一次
总成本为 1 * 4 + 1 * 4 + 1 * 4 = 12 。
可以证明不存在其他成本更低的映射方案。
注意按键 9 没有映射到任何字母：不必让每个按键都存在与之映射的字母，但是每个字母都必须映射到按键上。

示例 3：

输入：word = "aabbccddeeffgghhiiiiii"
输出：24
解释：图片中给出的重新映射方案的输入成本最小。
"a" -> 在按键 2 上按一次
"b" -> 在按键 3 上按一次
"c" -> 在按键 4 上按一次
"d" -> 在按键 5 上按一次
"e" -> 在按键 6 上按一次
"f" -> 在按键 7 上按一次
"g" -> 在按键 8 上按一次
"h" -> 在按键 9 上按两次
"i" -> 在按键 9 上按一次
总成本为 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 2 * 2 + 6 * 1 = 24 。
可以证明不存在其他成本更低的映射方案。

提示：

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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int minimumPushes(string word) { } };

golang 解法, 执行用时: 27 ms, 内存消耗: 6.4 MB, 提交时间: 2024-01-22 10:26:23

func minimumPushes(word string) (ans int) {
	cnt := [26]int{}
	for _, b := range word {
		cnt[b-'a']++
	}
	sort.Sort(sort.Reverse(sort.IntSlice(cnt[:])))

	for i, c := range cnt {
		ans += c * (i/8 + 1)
	}
	return
}

cpp 解法, 执行用时: 55 ms, 内存消耗: 23.7 MB, 提交时间: 2024-01-22 10:26:11

class Solution {
public:
    int minimumPushes(string word) {
        int cnt[26]{};
        for (char b: word) {
            cnt[b - 'a']++;
        }
        ranges::sort(cnt, greater<int>());

        int ans = 0;
        for (int i = 0; i < 26; i++) {
            ans += cnt[i] * (i / 8 + 1);
        }
        return ans;
    }
};

java 解法, 执行用时: 9 ms, 内存消耗: 44.6 MB, 提交时间: 2024-01-22 10:26:00

class Solution {
    public int minimumPushes(String word) {
        int[] cnt = new int[26];
        for (char b : word.toCharArray()) {
            cnt[b - 'a']++;
        }
        Arrays.sort(cnt);

        int ans = 0;
        for (int i = 0; i < 26; i++) {
            ans += cnt[25 - i] * (i / 8 + 1);
        }
        return ans;
    }
}

python3 解法, 执行用时: 137 ms, 内存消耗: 16.8 MB, 提交时间: 2024-01-22 10:25:48

'''
统计每个字母的出现次数，按照出现次数从大到小排序。
根据 排序不等式，出现次数前 8 大的字母，只需要按一次；
出现次数前 9 到 16 大的字母，需要按两次；依此类推。
把出现次数和对应的按键次数相乘再相加，得到的按键次数之和就是最小的。
'''
class Solution:
    def minimumPushes(self, word: str) -> int:
        a = sorted(Counter(word).values(), reverse=True)
        return sum(c * (i // 8 + 1) for i, c in enumerate(a))

上一题

下一题

详情