Re: [閒聊] 每日leetcode

[nh60211as (xXx_5354M3_31M0_xXx)]

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  https://i.imgur.com/YNJpGoH.png
https://i.imgur.com/G69mH5A.png  https://i.imgur.com/ptaX5iW.png
https://i.imgur.com/hEeZuph.png  https://i.imgur.com/mGTKAFz.png
https://i.imgur.com/gdejDOy.png  https://i.imgur.com/JX7AHZc.png
https://i.imgur.com/X6Pgqgi.png  https://i.imgur.com/mJ8dU86.png

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.71.204 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722944617.A.D7F.html