leetcode
leetcode 2001 ~ 2050
最少按键次数

最少按键次数

难度:

标签:

题目描述

代码结果

运行时间: 41 ms, 内存: 16.5 MB


/*
 * Leetcode Problem 2268: Minimum Key Presses
 * Using Java Stream to find the minimum key presses needed to type a list of words.
 * Each key press corresponds to a character, with the last few typed characters being free.
 */

import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Solution {
    public int minimumKeyPresses(String[] words) {
        // Stream through the array of words, split them into characters, and collect unique characters
        Set<Character> uniqueChars = Stream.of(words)
            .flatMapToInt(String::chars) // Convert each word to IntStream of chars
            .mapToObj(c -> (char) c) // Map to Character objects
            .collect(Collectors.toSet()); // Collect into a set of unique characters

        // The number of unique characters is the number of key presses required
        return uniqueChars.size();
    }
}

解释

方法:

此题解的思路是首先统计字符串 s 中每个字符出现的次数,然后将这些次数按照从大到小的顺序排序。对于按键次数的计算,我们知道最常出现的字符应该尽可能少按键,因此我们将出现次数最多的字符放在按键次数最少的位置。具体地,字符的按键次数计算公式为 (索引 // 9 + 1),意味着前9个最频繁的字符(索引0-8)需要按1次,接下来9个字符(索引9-17)需要按2次,依此类推。最终,将所有字符的按键次数与其出现次数的乘积加和,得到总的最少按键次数。

时间复杂度:

O(n + m log m)

空间复杂度:

O(m)

代码细节讲解

🦆
在该题解中,为什么要选择将字符出现的次数进行降序排序?
在该题解中,将字符出现次数进行降序排序是为了确保出现频率最高的字符被分配到按键次数最少的位置。这是因为频繁出现的字符如果按键次数较少,则可以显著减少总的按键次数。通过这种排序方式,可以将按键分配最优化,使得总的按键次数达到最小。
🦆
按键次数的计算公式`(索引 // 9 + 1)`是如何确保能最小化总按键次数的?
该计算公式`(索引 // 9 + 1)`是基于每9个字符一个按键次数等级来设计的。具体来说,索引从0开始,0到8的字符(共9个)需要按1次,索引9到17的下一组9个字符需要按2次,依此类推。这种分配方式确保了出现频率最高的字符(即排序后索引最小的字符)被分配到按键次数最少的组,从而在总的按键次数上实现最小化。
🦆
如果存在多个字符出现次数相同,排序时是否会影响最终的按键次数结果?
如果多个字符出现次数相同,它们在排序后的具体顺序对最终的总按键次数没有影响。这是因为相同频率的字符不论如何排序,它们最终被分配到的按键次数等级是相同的。因此,即使排序结果在相同频率字符之间有所不同,总按键次数仍将保持不变。

相关问题