「算法刷题」哈希表的相关经典题目

Posted on 2021-10-29 Edited on 2024-02-02

LeetCode题目	相关题目类型	相关链接
383	赎金信（简单难度）	383. 赎金信 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26]={0};
        // 记录magazine里各个字符出现的次数
        for(int i=0;i<magazine.length();i++){
            record[magazine[i]-'a']++;
        }
        // 遍历ransomNote，在record里对应的字符个数做--操作
        for(int j=0;j<ransomNote.length();j++){
            record[magazine[i]-'a']--;
            // 如果小于零，说明ransomNote里出现的字符，magazine里没有
            if(record[magazine[i]-'a']<0){
                return false;
            }
        }
        return true;
        

    }
};

类似题目：

LeetCode题目	相关题目类型	相关链接
242	有效的字母异位词（简单难度）	242. 有效的字母异位词 - 力扣（LeetCode） (leetcode-cn.com)

数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。

定义一个数组叫做record用来上记录字符串s里字符出现的次数。

1、需要把字符映射到数组也就是哈希表的索引下表上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下表0，相应的字符z映射为下表25。

再遍历字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数，统计出来了。

2、那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。

3、那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。

最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。

时间复杂度为O(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为O(1)。

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
            record[s[i] - 'a']++;
        }
        for (int i = 0; i < t.size(); i++) {
            record[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (record[i] != 0) {
                // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        // record数组所有元素都为零0，说明字符串s和t是字母异位词
        return true;
    }
};

知识补充：

1、c++ memset()函数

memset 函数是内存赋值函数，用来给某一块内存空间进行赋值的；

包含在<string.h>头文件中,可以用它对一片内存空间逐字节进行初始化；

原型为：

void *memset(void *s, int v, size_t n);

这里s可以是数组名，也可以是指向某一内在空间的指针；

v为要填充的值；

n为要填充的字节数；

示例1：

struct data
{
char num[100];
char name[100];
int  n;
};
struct data  a, b[10];

memset( &a, 0, sizeof(a) ); //注意第一个参数是指针类型，a不是指针变量，要加&
memset( b, 0, sizeof(b) );  //b是数组名，就是指针类型，不需要加&

示例2：

char str[9];

//我们用memset给str初始化为“00000000”，用法如下

memset(str,0,8); 

//注意，memset是逐字节 拷贝的。

示例3：

int num[8];

//我们用memset给str初始化为{1,1,1,1,1,1,1,1}，
memset(num,1,8);//这样是不对的

//一个int是4个字节的，8个int是32个字节，所以首先要赋值的长度就不应该为8而是32。

//因为memset是 逐字节 拷贝，以num为首地址的8字节空间都被赋值为1，

//即一个int变为0X00000001 00000001 00000001 00000001，显然，把这个数化为十进制不会等于1的

2、常见的 string 类构造函数有以下几种形式：

strings(num, c) //生成一个字符串，包含num个c字符

LeetCode题目	相关题目类型	相关链接
1002	查找常用字符（简单难度）	1002. 查找共用字符 - 力扣（LeetCode） (leetcode-cn.com)

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']++;
        }

        int hashOtherStr[26] = {0}; // 统计除第一个字符串外字符的出现频率
        for (int i = 1; i < words.size(); i++) {
            memset(hashOtherStr, 0, 26 * sizeof(int));
            for (int j = 0; j < words[i].size(); j++) {
                hashOtherStr[words[i][j] - 'a']++;
            }
            // 更新hash，保证hash里统计26个字符在所有字符串里出现的最小次数
            for (int k = 0; k < 26; k++) {
                hash[k] = min(hash[k], hashOtherStr[k]);
            }
        }
        // 将hash统计的字符次数，转成输出形式
        for (int i = 0; i < 26; i++) {
            while (hash[i] != 0) { // 注意这里是while，多个重复的字符
                string s(1, i + 'a'); // char -> string
                result.push_back(s);
                hash[i]--;
            }
        }

        return result;

    }
};

知识补充：

哈希数据结构：unordered_set

参考链接： C++ STL unordered_set容器完全攻略 (biancheng.net)

注意题目特意说明：输出结果中的每个元素一定是唯一的，也就是说输出的结果是去除了重复的元素，同时可以不考虑输出结果的顺序

那么用数组来做哈希表也是不错的选择，例如242. 有效的字母异位词

但是要注意，使用数组来做哈希的题目，是因为题目都限制了数值的大小。

而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

此时就要使用另一种结构体了，set ，关于set，C++ 给提供了如下三种可用的数据结构：

std::set
std::multiset
std::unordered_set

std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表，使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。

c++ unordered_set容器的成员方法：

find(key): 查找以值为 key 的元素，如果找到，则返回一个指向该元素的正向迭代器；反之，则返回一个指向容器中最后一个元素之后位置的迭代器（如果 end() 方法返回的迭代器）。

思路如图所示：

LeetCode题目	相关题目类型	相关链接
349	两个数组的交集（简单难度）

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for (int num : nums2) {
            // 下面的代码表示：发现nums2的元素 在nums_set里又出现过
            //不理解的话，复习unordered_set的成员方法
            if (nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

拓展

那有同学可能问了，遇到哈希问题我直接都用set不就得了，用什么数组啊。

直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。

不要小瞧这个耗时，在数据量大的情况，差距是很明显的。

LeetCode题目	相关题目类型	相关链接
350	两个数组的交集2（简单难度）	350. 两个数组的交集 II - 力扣（LeetCode） (leetcode-cn.com)

这道题和349不一样，没有要求输出不能重复

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        // 对两个数组进行排序
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        int i=0,j=0;
        vector<int> res;
        //同时对两个数组遍历，有一个遍历完就结束
        while(i<nums1.size() && j<nums2.size()){
            // 相等，则添加到结果里
            if(nums1[i]==nums2[j]){

                res.push_back(nums1[i]);
                ++i;
                ++j;
            }
            else if(nums1[i]<nums2[j])
                ++i;
            else                    
               ++j;
        }
        return res;
    }
};

LeetCode题目	相关题目类型	相关链接
202	快乐数（简单难度）	202. 快乐数 - 力扣（LeetCode） (leetcode-cn.com)

题目中说了会无限循环，即在求和的过程中，sum会重复出现，这一点对解题很重要。

正如：关于哈希表，你该了解这些！中所说，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。

这道题用哈希法，来判断这个sum是否重复出现，重复则return false，否则一直找到sum为1为止。

判断sum是否重复出现就可以使用unordered_set。

class Solution {
public:
    // 取数值各个位上的单数之和
    int getSum(int n) {
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        while(1) {
            int sum = getSum(n);
            if (sum == 1) {
                return true;
            }
            // 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
            if (set.find(sum) != set.end()) {
                return false;
            } else {
                set.insert(sum);
            }
            n = sum;
        }
    }
};

LeetCode题目	相关题目类型	相关链接
1	（简单难度）	1. 两数之和 - 力扣（LeetCode）

则要使用map，那么来看一下使用数组和set来做哈希法的局限。

数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。

set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。

此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下表。

C++中map，有三种类型：

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::map	红黑树	key有序	key不可重复	key不可修改	O(logn)	O(logn)
std::multimap	红黑树	key有序	key可重复	key不可修改	O(logn)	O(logn)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。

同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。更多哈希表的理论知识请看关于哈希表，你该了解这些！。

这道题目中并不需要key有序，选择std::unordered_map 效率更高！

解题思路：

例如：nums=[2,7,11,15],target=9

遍历数组

1、寻找target-nums[i]是否在map中，

2、没有，9-2=7,7不在map中，把2和对应下标0放进map中

3、有，9-7=2,2在map中，找到了数值2和7相加等于9，返回其下标

遍历结束后，没有返回值，则返回空的数组

参考链接： C++ STL unordered_map容器用法详解 (biancheng.net)

C++代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map <int,int> map;//创建空的umap容器
        for(int i = 0; i < nums.size(); i++) {
            //查找target - nums[i]是否在map中，
            auto iter = map.find(target - nums[i]);
            // 有，返回两个数的下标
            if(iter != map.end()) {
                return {iter->second, i};
            }
            // 没有，把该数值和其下标加入到map中
            map.insert(pair<int, int>(nums[i], i));
        }
        //没找到
        return {};
    }
};

LeetCode题目	相关题目类型	相关链接
49	（中等难度）	49. 字母异位词分组 - 力扣（LeetCode） (leetcode-cn.com)

参考链接：https://blog.csdn.net/fuqiuai/article/details/83589593

解题思路：

1、对字符串每个词的字母按照字典序进行排序，异位词对字母进行排序后有相同的字母序列。

用排序后的字母序列作为map的key，将所有异位词都保存到字符串数组中，用map建立key和字符串数组之间的映射（不需要结果有序，所以用unordered map)

2、最后把归纳好的字符串数组存入结果res中。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        if(strs.size()==0)return res;
        // 键为string字符串类型，值为字符串数组类型
        unordered_map<string,vector<string>> map1;
        for(int i=0;i<strs.size();i++){
            string s=strs[i];
            sort(s.begin(),s.end());
            // 排序后相同的字符串放到一个数组里，键为排序后的字符串
            map1[s].push_back(strs[i]);//map1[s]是一个值类型为字符串的数组
        }
        for(auto v:map1){
            res.push_back(v.second);
        }
        return res;
    }
};

知识补充：

1、c++ memset()函数

2、 常见的 string 类构造函数有以下几种形式：

知识补充：

哈希数据结构：unordered_set

c++ unordered_set容器的成员方法：

拓展

2、常见的 string 类构造函数有以下几种形式：