最少按键次数
难度:
标签:
题目描述
代码结果
运行时间: 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)`是如何确保能最小化总按键次数的?
▷🦆
如果存在多个字符出现次数相同,排序时是否会影响最终的按键次数结果?
▷