2024-08-06
3016. Minimum Number of Pushes to Type Word II
You are given a string word containing lowercase English letters.
Telephone keypads have keys mapped with distinct collections of lowercase
English letters, which can be used to form words by pushing them. For
example, the key 2 is mapped with ["a","b","c"], we need to push the key one
time to type "a", two times to type "b", and three times to type "c" .
It is allowed to remap the keys numbered 2 to 9 to distinct collections of
letters. The keys can be remapped to any amount of letters, but each letter
must be mapped to exactly one key. You need to find the minimum number of
times the keys will be pushed to type the string word.
Return the minimum number of pushes needed to type word after remapping the
keys.
有点像 hamming code 还是什么碗糕
会希望出现频率越高的 cost 越低
所以就是先扫过去计算每个的出现次数
然后出现次数从大排到小
从最频繁出现的开始 assign 按1次 按2次...
顺便计算总共要按几次
class Solution {
public:
int minimumPushes(string word) {
vector<int> count(26);
for (auto c : word) {
count[c - 'a']++;
}
sort(count.begin(), count.end(), greater<>());
int result = 0;
int push = 0;
for (int i = 0; i < count.size(); ++i) {
if (i % 8 == 0){
push++;
}
result += push * count[i];
}
return result;
}
};