[哈希表] lc-1002. 查找常用字符

文章目录

1. 题目来源

链接：1002. 查找常用字符

2. 题目说明

3. 题目解析

简单的哈希表的应用，由于均为小写字母，则映射到数字后范围就是 [ 0 , 26 ] [0,26] [0,26] 之间的整数，不限单词的前后顺序，找到各个单词中均重复的字母。

可以针对每一个字符串进行哈希映射，形成一个二维哈希映射表，在每一列中寻找最小的哈希值就是该映射字符的出现次数。

具体可以看看这个中间输出的哈希表，很容易理解。

在本题中，最后处理输出时，需要将数字 0，处理为字符串 "a" 这种形式，一般我们可以通过：

sting s;
char c = i + 'a';
s = c + "";

这种方式实现整形到字符串类型的转换。

在官方题解中有 C++11 的新操作：res.emplace_back(1, i + 'a');

• 相当于调用 string 的构造函数，往里面 push 一个 string(1,i+'a')。string(size_type n,char c) 是创建一个包含 n 个字符的 string 对象，其中每个字符都是 c。

具体可以参考 emplace_back 与 push_back 的区别及它自身的新特性。

参见代码如下：

class Solution {
public:
    vector<string> commonChars(vector<string>& A) {
        vector<string> res;
        vector<vector<int>> hash(A.size(), vector<int>(26));
        for (int i = 0; i < A.size(); ++i) 
            for (int j = 0; j < A[i].size(); ++j) 
                hash[i][A[i][j] - 'a'] ++;

        for (auto e:hash) {

            for (auto s:e) 
                cout << s << ' ';
            cout << endl;
        }

        int i = 25;
        for (i; i >= 0; --i) {
            int t = 0x3f3f3f3f;
            for (int j = 0; j < A.size(); ++j) {
                t = min(t, hash[j][i]);
            }
            while (t) res.emplace_back(1, i + 'a'), --t;
        }
        return res;
    }
};