Re: [閒聊] 每日leetcode
看板Marginalman作者smart0eddie (smart0eddie)時間1年前 (2024/08/06 09:19)推噓1(1推 0噓 3→)留言4則, 3人參與討論串646/1548 (看更多)
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;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.173.211.221 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722907148.A.3F7.html
推
08/06 09:21,
1年前
, 1F
08/06 09:21, 1F
→
08/06 09:34,
1年前
, 2F
08/06 09:34, 2F
→
08/06 09:49,
1年前
, 3F
08/06 09:49, 3F
→
08/06 09:49,
1年前
, 4F
08/06 09:49, 4F
討論串 (同標題文章)
完整討論串 (本文為第 646 之 1548 篇)：