Re: [閒聊] 每日leetcode

看板Marginalman作者nh60211as (xXx_5354M3_31M0_xXx)時間1年前 (2024/08/06 19:43)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串653/1550 (看更多)

3016. Minimum Number of Pushes to Type Word II 思路：把頻率最高的放在 8 個按鈕最前面，越低的越後面實作： (1) 用 map 把各個字母的頻率收集起來 (2) 由高到低排序 (3) 每 8 個字母一起加總，要考慮 residual 運氣好很久以前寫過 residual iteration https://github.com/nh60211as/WorldChunkToolCPP/blob/master/WorldChunkToolCPP/ ChunkDecrypter.cpp class Solution { public: int minimumPushes(string word) { map<char, int> frequency; for (char c : word) { frequency[c]++; } vector<int> descendingFrequency; descendingFrequency.reserve(frequency.size()); for (auto const& [key, val] : frequency) { descendingFrequency.push_back(val); } sort(descendingFrequency.rbegin(), descendingFrequency.rend()); constexpr int BUTTON_COUNT = 8; int result = 0; int pushRequired = 1; size_t i = 0; for (; i < (descendingFrequency.size() / BUTTON_COUNT) * BUTTON_COUNT; i += BUTTON_COUNT) { result += pushRequired * subVectorSum(descendingFrequency, i, i + BUTTON_COUNT); pushRequired++; } // residual for (; i < descendingFrequency.size(); i++) { result += pushRequired * descendingFrequency[i]; } return result; } private: static int subVectorSum(const vector<int>& vec, size_t begin, size_t end) { end = min(vec.size(), end); return accumulate( next(vec.begin(), begin), next(vec.begin(), end), 0); } }; -- https://i.imgur.com/07Uv9NC.png