C++字符串数组存哈希表

引用[1]中提到了一种使用数组类型哈希表的方法来存储字符串数组。这种方法利用数组的简单和快捷的特点，将字符串中的每个字符出现的次数存入哈希表中。首先，取第一个字符串，读取其中的每一个字符出现次数，存入哈希表hash中，并以此为参照对象。然后，遍历剩余的字符串，创建另一个哈希表hashOther，记录剩余字符串中字符的出现频率。每次读取后，将其与第一个字符串形成的哈希表相比较，取两者中的最小值，实时更新hash哈希表。这样，最终的hash哈希表中存储了26个字符在所有字符串中出现的最小次数。[1][3]

相关问题

​C++，已知一组包含至少8个字符的数组及各字符的出现概率（随机产生）。求该字符串数组的哈夫曼编码及平均码长。（给出完整代码）

在C++中，我们可以使用优先队列（priority_queue）和哈夫曼树（Huffman Tree）的概念来计算给定字符的概率对应的哈夫曼编码。这是一个典型的动态规划问题。首先，我们需要创建一个哈夫曼节点结构体，然后按照概率构建二叉树，并生成哈夫曼编码。下面是一个简单的示例代码：

#include <iostream>
#include <queue>
#include <vector>
#include <string>

// 定义哈夫曼节点
struct HuffmanNode {
    char data;
    int freq;
    HuffmanNode* left = nullptr;
    HuffmanNode* right = nullptr;
    HuffmanNode(char ch, int f) : data(ch), freq(f) {}
};

// 计算频率总和
int totalFreq(const std::vector<HuffmanNode*>& nodes) {
    int sum = 0;
    for (const HuffmanNode* node : nodes)
        sum += node->freq;
    return sum;
}

// 插入节点到堆
void insert(HuffmanNode*& root, HuffmanNode* newNode) {
    if (!root || newNode->freq < root->freq)
        root = newNode;
    else {
        HuffmanNode* temp = root;
        root = newNode;
        if (newNode->freq < temp->freq)
            newNode->left = temp;
        else
            newNode->right = temp->left;
        temp->left = newNode->right;
    }
}

// 构建哈夫曼树
std::pair<HuffmanNode*, HuffmanNode*> buildHuffmanTree(const std::vector<HuffmanNode*>& nodes) {
    std::priority_queue<std::pair<HuffmanNode*, int>, std::vector<std::pair<HuffmanNode*, int>>, std::greater<> > pq(nodes.begin(), nodes.end());
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top().first;
        pq.pop();
        HuffmanNode* right = pq.top().first;
        pq.pop();
        HuffmanNode* newNode = new HuffmanNode('\0', left->freq + right->freq);
        newNode->left = left;
        newNode->right = right;
        insert(pq, newNode);
    }
    return pq.top();
}

// 生成哈夫曼编码
std::string getHuffmanCode(HuffmanNode* root, const std::string& prefix, std::map<char, std::string>& codes) {
    if (root == nullptr) return "";
    if (root->data != '\0') {
        codes[root->data] = prefix;
    } else {
        getHuffmanCode(root->left, prefix + "0", codes);
        getHuffmanCode(root->right, prefix + "1", codes);
    }
    return codes;
}

// 主函数
void computeHuffmanCoding(const std::vector<std::pair<char, int>>& probabilities) {
    std::vector<HuffmanNode*> nodes;
    for (auto prob : probabilities) {
        nodes.push_back(new HuffmanNode(prob.first, prob.second));
    }

    // 构建哈夫曼树
    auto [root, dummy] = buildHuffmanTree(nodes);

    // 获取并存储哈夫曼编码
    std::map<char, std::string> huffmanCodes;
    getHuffmanCode(root, "", huffmanCodes);

    // 计算平均码长
    double averageCodeLength = 0;
    for (auto& pair : huffmanCodes) {
        averageCodeLength += static_cast<double>(pair.second.length()) * pair.second[0];
    }
    averageCodeLength /= huffmanCodes.size();

    std::cout << "Huffman Codes: ";
    for (const auto& code : huffmanCodes)
        std::cout << code.first << ": " << code.second << ", ";

    std::cout << "\nAverage Code Length: " << averageCodeLength << std::endl;
}

int main() {
    // 示例数据，实际应用中需要从输入或概率数组获取
    std::vector<std::pair<char, int>> probabilities = {{"a", 50}, {"b", 30}, {"c", 20}};
    computeHuffmanCoding(probabilities);
    return 0;
}

请注意，这个代码只是一个简化的版本，实际项目中可能需要处理更多的边界情况和优化。此外，上述代码假设输入的字符集不会很大，如果字符集非常大，可以考虑使用哈希表而不是直接使用`std::map`。

C++ 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。 返回所有串联字串在 s 中的开始索引。你可以以 任意顺序 返回答案。

这是一个经典的字符串问题，可以使用滑动窗口和哈希表来解决。

具体实现如下：

vector<int> findSubstring(string s, vector<string>& words) {
    vector<int> res;
    if (s.empty() || words.empty()) {
        return res;
    }
    int word_len = words[0].size();
    int total_len = words.size() * word_len;
    unordered_map<string, int> word_dict;
    for (const auto& word : words) {
        ++word_dict[word];
    }
    for (int i = 0; i <= (int)s.size() - total_len; ++i) {
        unordered_map<string, int> cur_dict;
        int j = i;
        while (j < i + total_len) {
            string cur_word = s.substr(j, word_len);
            if (word_dict.count(cur_word) == 0) {
                break;
            }
            ++cur_dict[cur_word];
            if (cur_dict[cur_word] > word_dict[cur_word]) {
                break;
            }
            j += word_len;
        }
        if (j == i + total_len) {
            res.push_back(i);
        }
    }
    return res;
}

其中，word_dict 是存储 words 数组中所有字符串的哈希表，cur_dict 是存储当前子串中所有字符串的哈希表。在每次移动滑动窗口时，需要将相应的单词从哈希表中删除或加入。由于需要求出所有符合条件的子串，因此需要遍历所有可能的起始位置，并将符合条件的起始位置存入结果数组中。