• 【LeetCode1002. 查找共用字符】——数组型哈希表


    1002. 查找共用字符

    给你一个字符串数组 words ,请你找出所有在 words 的每个字符串中都出现的共用字符( 包括重复字符),并以数组形式返回。你可以按 任意顺序 返回答案。

    示例 1:

    输入:words = ["bella","label","roller"]
    输出:["e","l","l"]
    
    • 1
    • 2

    示例 2:

    输入:words = ["cool","lock","cook"]
    输出:["c","o"]
    
    • 1
    • 2

    提示:

    • 1 <= words.length <= 100
    • 1 <= words[i].length <= 100
    • words[i] 由小写英文字母组成

    思考:

    本题又是一道经典的哈希表问题,通过运用哈希表可以做到很容易地记录每个字符的出现次数。根据题意,我们需要寻找的是所有字符串中的共用字符,值得注意的是,题意中表示是包括重复字符的,这就在最后输出的时候要多加注意。

    所以我们可以通过统计每个字符串中字符的出现次数,并统计出其中每个字符在不同字符串中出现频率的最小值。若最小频率为0,则说明该字符并不是共用字符。频率为1,则说明每个字符串都出现了一次该字符,频率2则是都出现了两次,一次类推。

    数组哈希表:

    此处我还是使用的数组类型哈希表,因为哈希表中一共只需要存储26个字符元素,利用数组比较简单快捷。首先,取第一个字符串,读取其中的每一个字符出现次数,存入哈希表hash中,并以此为参照对象。

            //考虑空数组情况
            if (words.size() == 0)
            {
                return result;
            }
    
            int hash[26] = { 0 }; //初始化哈希表,用于存放字符出现的最少次数
            for (int i = 0; i < words[0].size(); i++) //将第一个字符串所含字符存入hash
            {
                hash[words[0][i] - 'a']++; //以ASCII码的形式记录
            }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    当然,我们需要提前考虑空数组的情况。

    接着我选择创建另一个哈希表hashOther,用来读取剩下的字符串。每次读取后,都与第一个字符串形成的哈希表相比较,频率取两者中的最小值,实时更新hash哈希表(作为参照的哈希表)

            int hashOther[26] = { 0 }; //定义另一个哈希表,记录剩余字符串中字符的出现频率
            for (int i = 1; i < words.size(); i++) { //外层遍历剩余的字符串
                memset(hashOther, 0, 26 * sizeof(int)); //清空哈希表
    
                for (int j = 0; j < words[i].size(); j++) { //内层遍历每个子字符串中字符
                    hashOther[words[i][j] - 'a']++;
                }
                // 更新hash,保证hash里统计26个字符在所有字符串里出现的最小次数
                for (int k = 0; k < 26; k++) {
                    hash[k] = min(hash[k], hashOther[k]); //使用min函数进行更新
                }
            }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    其中值得一提的是,每次新遍历一个新的字符串,都必须在此初始化hashOther哈希表,否则字符出现的频率会不断叠加。这里使用的是memset函数

    函数原型:

    void *memset(void *s,int c,unsigned long n);
    
    • 1

    函数功能:为指针变量s所指的前n个字节内存单元填充给定的int型数值c,它可以为任何数据进行初始化。换句话说,就是将数值c以单个字节逐个拷贝的方式放到指针变量s所指的内存中去。 注意:只将数值c的最低一个字节填充到内存。

            int hashOther[26] = { 0 }; //定义另一个哈希表,记录剩余字符串中字符的出现频率
            for (int i = 1; i < words.size(); i++) { //外层遍历剩余的字符串
                memset(hashOther, 0, 26 * sizeof(int)); //清空哈希表
    
                for (int j = 0; j < words[i].size(); j++) { //内层遍历每个子字符串中字符
                    hashOther[words[i][j] - 'a']++;
                }
                // 更新hash,保证hash里统计26个字符在所有字符串里出现的最小次数
                for (int k = 0; k < 26; k++) {
                    hash[k] = min(hash[k], hashOther[k]); //使用min函数进行更新
                }
            }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    最后就是输出结果了,遍历hash哈希表,判断其中出现频率不为0的字符,在将char类型字符转换为string类型输出。

        // 将hash统计的字符次数,转成输出形式
        for (int i = 0; i < 26; i++) {
            while (hash[i] != 0) { // 使用while,可以输出多个同样的字符
                string s(1, i + 'a'); // 将char转化为string
                result.push_back(s); //更新result
                hash[i]--;
            }
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    完整代码(C++):

    #include
    #include
    
    using namespace std;
    
    class Solution {
    public:
        vector<string> commonChars(vector<string>& words) {
            vector<string> result; //定义结果数组
    
            //考虑空数组情况
            if (words.size() == 0)
            {
                return result;
            }
    
            int hash[26] = { 0 }; //初始化哈希表,用于存放字符出现的最少次数
            for (int i = 0; i < words[0].size(); i++) //将第一个字符串所含字符存入hash
            {
                hash[words[0][i] - 'a']++; //以ASCII码的形式记录
            }
            int hashOther[26] = { 0 }; //定义另一个哈希表,记录剩余字符串中字符的出现频率
            for (int i = 1; i < words.size(); i++) { //外层遍历剩余的字符串
                memset(hashOther, 0, 26 * sizeof(int)); //清空哈希表
    
                for (int j = 0; j < words[i].size(); j++) { //内层遍历每个子字符串中字符
                    hashOther[words[i][j] - 'a']++;
                }
                // 更新hash,保证hash里统计26个字符在所有字符串里出现的最小次数
                for (int k = 0; k < 26; k++) {
                    hash[k] = min(hash[k], hashOther[k]); //使用min函数进行更新
                }
            }
    
            // 将hash统计的字符次数,转成输出形式
            for (int i = 0; i < 26; i++) {
                while (hash[i] != 0) { // 使用while,可以输出多个同样的字符
                    string s(1, i + 'a'); // 将char转化为string
                    result.push_back(s); //更新result
                    hash[i]--;
                }
            }
            return result;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    参考教程:

    代码随想录

    C++中memset函数详解_abtgu的博客-CSDN博客_c++ memset


    往期回顾:
    LeetCode142. 环形链表 II
    面试题 02.07. 链表相交
    LeetCode19. 删除链表的倒数第 N 个结点
    LeetCode24. 两两交换链表中的节点
    LeetCode206. 反转链表
    LeetCode707.设计链表
    LeetCode203.移除链表元素
    LeetCode54. 螺旋矩阵
    LeetCode59.螺旋矩阵II
    LeetCode977.有序数组的平方
    LeetCode844.比较含退格的字符串
    LeetCode283.移动零
    LeetCode27.移除元素
    LeetCode26.删除有序数组中的重复项
    LeetCode209.长度最小的子数组
    LeetCode904. 水果成篮
    LeetCode242.有效的字母异位词
    LeetCode76.最小覆盖子串

  • 相关阅读:
    用什么方式推广莆田鞋最好?C原版本真的能买吗
    【数据结构】树Tree
    2022/11/28-29总结
    【Bluetooth|蓝牙开发】一、开篇词 | 打造全网最详细的Bluetooth开发教程
    AMSR/ADEOS-II L1A Raw Observation Counts V003地球表面和大气微波辐射的详细观测数据
    Vue实现过渡动画的三种方式
    Linux进阶-ipc管道
    JavaScript闭包
    汽车虚拟仿真技术的实现、应用和未来
    终于有人把操作系统、网络系统、线程进程、IO模型全部总结出来了
  • 原文地址:https://blog.csdn.net/weixin_51630192/article/details/127820422