LeetCode 3016. 输入单词需要的最少按键次数 II 带注释
原题链接
中等
作者:
蓬蒿人
,
2024-01-21 14:46:30
,
所有人可见
,
阅读 37
//延续第一题思路
// 26个字母要在2~9 8个键位上实现
// 那么 就会有6个键位可以输入3个字母 2个键位可以输入4个字母
// 所有字符分配到包含字母最少的键位去 也就是2~9 一遍一遍分配过去
// 对于第i个字母 要输入ta的次数就是(i/8)+1
// 上面是第一题的思路
// 对于本题 要按下的总次数最少 必然是要出现次数越多的字母越快按出来
// 所以 统计所有字母出现次数
// 第1~8高频字母按一次 9~16高频字母按2次
// 17~24 3 25~26 4
// 最后累计出现次数*要按几下 就有答案了
class Solution {
public:
int minimumPushes(string w) {
unordered_map<char,int> mp;//记录每个字符出现次数
for (auto x:w) {
mp[x]++;
}
string s;//将26个字符以出现次数降序排序
for (int i=0;i<26;i++) {//构造ing
char t='a'+i;
s+=t;
}
sort(s.begin(),s.end(),[&](char a,char b) {//建议用lambda表达式
return mp[a]>mp[b];
});
int ans=0;//26*4*1e5<1e9 int存的下
for (int i=0;i<26;i++) {
ans+=mp[s[i]]*((i/8)+1);//出现次数*要按几下
}
return ans;
}
};