leetcode 1002 查找常用字符

Bertha 。 2022-09-09 02:24 101阅读 0赞

## 前言 ##

题目：[1002. 查找常用字符][1002.]

参考答案：[1002. 查找常用字符-力扣官方题解][1002. _-]

--------------------

## 提交代码 ##

如果你之前做过[leetcode 242 有效的字母异位词][leetcode 242]，这道题目毫无难度。统计每个字符串中的字母出现次数就成。

#include <vector>
    #include <string>
    #include <iostream>
    
    using namespace std;
    
    class Solution {
    public:
        vector<string> commonChars(vector<string>& words) {
            vector<string> result;
    
            // 二维数组。每一行用于统计一个字符串的字母出现次数
            vector<vector<int>> letters_statistical(words.size(),vector<int>(26,0));
    
            // 将字母出现次数，统计入数组
            for(int i=0; i<words.size(); i++){
                for(auto ch : words[i]){
                    letters_statistical[i][ch-'a']++;
                }
            }
    
            // 按列统计。该列中不存在零时，求该列的最小值
            for(int col=0; col<26; col++){
                int min = INT32_MAX;
                int row=0;
                for(; row<words.size(); row++){
                    if(letters_statistical[row][col]==0)
                        break;
                    min = letters_statistical[row][col] < min ? letters_statistical[row][col] : min;
                }
                if(row==words.size()){
                    while(min--)
                        result.push_back(string(1,char('a'+col)));
                }
            }
    
            return result;
        }
    };
    
    
    int main(void){
        vector<string> words = {"bella","label","roller"};
    
        Solution s;
    
        vector<string> result = s.commonChars(words);
    
        for(auto s : result)
            cout<<s<<" ";
    }

### 答案实现 ###

答案和上面的代码思路相同，但是答案代码处理的更好，即便读取边统计/处理。这节省了很多的附加空间。

class Solution {
    public:
        vector<string> commonChars(vector<string>& words) {
            vector<int> minfreq(26, INT_MAX);
            vector<int> freq(26);
            for (const string& word: words) {
                fill(freq.begin(), freq.end(), 0);
                for (char ch: word) {
                    ++freq[ch - 'a'];
                }
                for (int i = 0; i < 26; ++i) {
                    minfreq[i] = min(minfreq[i], freq[i]);
                }
            }
    
            vector<string> ans;
            for (int i = 0; i < 26; ++i) {
                for (int j = 0; j < minfreq[i]; ++j) {
                    ans.emplace_back(1, i + 'a');
                }
            }
            return ans;
        }
    };

[1002.]: https://leetcode-cn.com/problems/find-common-characters/
[1002. _-]: https://leetcode-cn.com/problems/find-common-characters/solution/cha-zhao-chang-yong-zi-fu-by-leetcode-solution/
[leetcode 242]: https://blog.csdn.net/sinat_38816924/article/details/119966493