题解 | #字符编码#

这道题算最短的编码，因此我们采用构造哈夫曼树。首先我们先解析出一行字符串里每个字符的出现次数，用std::map 进行保存。然后我们使用队列来构造哈夫曼树。

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <exception>
#include <functional>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <ostream>
#include <stack>
#include <vector>
class StrEncode {
    struct haff_node_t {
        int weight;
        bool is_leaf;
        char data;
        int height = 0;
        std::shared_ptr<haff_node_t> left, right;
        haff_node_t(haff_node_t& node) {
            weight  = node.weight;
            is_leaf = node.is_leaf;
            data    = node.data;
            left    = node.left;
            right   = node.right;
        }
        explicit haff_node_t(int weight, bool is_leaf = false, char data = '\0')
            : weight(weight), is_leaf(is_leaf), data(data) {}
        explicit haff_node_t(const std::pair<char, int>& p) {
            this->data    = p.first;
            this->weight  = p.second;
            this->is_leaf = true;
        }
        bool operator<(const haff_node_t& node) const {
            return this->weight < node.weight;
        }
        bool operator>(const haff_node_t& node) const {
            return this->weight > node.weight;
        }
        bool operator==(const haff_node_t& node) const {
            return this->data == node.data;
        }
        bool operator==(const char& c) const {
            return this->data == c;
        }
        bool static cmp_greater(const haff_node_t& n1, const haff_node_t& n2) {
            return n1 > n2;
        }
        static bool cmp_greater_inptr(
            const std::shared_ptr<haff_node_t>& n1,
            const std::shared_ptr<haff_node_t>& n2) {
            if (n1.get() && n2.get()) {
                return n1->weight > n2->weight;
            }
            throw std::runtime_error("pointers are null");
        }
    };

  public:
    static void solve(const std::string& line) {
        std::map<char, int> mp;
        int min_encode_len = 0;
        for (const auto& c : line) {
            if (mp.find(c) == mp.end()) {
                mp[c] = 1;
            } else {
                mp[c]++;
            }
        }
        std::vector<std::shared_ptr<haff_node_t>> node_vec;
        node_vec.reserve(mp.size());
        for (auto& m : mp) {
            node_vec.push_back(std::make_shared<haff_node_t>(m));
        }
        std::sort(
            node_vec.begin(), node_vec.end(), haff_node_t::cmp_greater_inptr);
        while (node_vec.size() > 1) {
            auto right = node_vec.back();
            node_vec.pop_back();
            auto left = node_vec.back();
            node_vec.pop_back();

            auto new_node = std::make_shared<haff_node_t>(
                                right->weight + left->weight);
            new_node->left  = left;
            new_node->right = right;
            node_vec.push_back(new_node);
            if (!new_node->is_leaf) {
                min_encode_len += new_node->weight;
            }
            std::sort(
                node_vec.begin(), node_vec.end(),
                haff_node_t::cmp_greater_inptr);
        }
        std::cout << min_encode_len << std::endl;
    }
};
int main() {
    std::string line;
    while (getline(std::cin, line)) { // 注意 while 处理多个 case
        StrEncode::solve(line);
    }
}
// 64 位输出请用 printf("%lld")