LeedCode刷题:1002.查找常用字符

解题思想:字符串中字符出现频率取交集,最终将交集中的字符都计入结果

创建一个最小频率数组minfreq,和临时频率数组tmp;

遍历字符串数组,每次遍历前将临时tmp置0,然后计算每个字符频率,遍历一个字符串后就将tmp和minfreq进行取交集,即更新minfreq值

最终构造结果集,对26个字母的公共最小出现频率计入结果

class Solution {
public:
    vector<string> commonChars(vector<string>& A) {
        // 构造两个数组,存放字符出现频率和最小出现频率
        vector<int> minfreq(26,INT_MAX);
        vector<int> freq(26);//遍历每个字符串时来临时存放出现频率
        // 遍历A,且每次遍历都要freq置全0
        // 统计每个字符串中每个字符出现频率
        for(const string &word:A){
            fill(freq.begin(),freq.end(),0);//清空
            for(char c:word){//遍历字符
                freq[c-'a']++;//统计
            }
            for(int i=0;i<26;i++){//将每个字符串的freq和minfreq取交集,更新minfreq值
                minfreq[i]=min(minfreq[i],freq[i]);
            }
        }
        // 构造结果集
        vector<string> res;
        // 对26个字符进行统计,有的字符没有在全部字符串中出现,或没出现过,则minfreq为0则不统计
        // 其他出现多次的统统计入结果
        for(int i=0;i<26;i++){
            for(int j=0;j<minfreq[i];j++){
                res.emplace_back(1,i+'a');//出现minfreq[i]次,便显示多少次,即插入多少次
            }
        }
        return res;
    }
};

 

上一篇:B-1002 写出这个数 (20 分)


下一篇:1002 写出这个数 (20 分)