Leetcode哈希篇总结（c++）_leetcode hash

注：按照代码随想录的刷题指南进行，自己总结补充，以加深印象
参考链接：https://leetcode-cn.com/circle/article/wGp7Y9/
题目来源：力扣（LeetCode）

一、基础知识

1、hash ，也成散列表， 定义略。

2、hash碰撞的解决方法：

拉链法：在碰撞的位置添加链表额外存储，因此要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间
线性探测法：：如果发生冲突，则将该数据放入后面的第一个空位中。因此要求哈希表的大小要比数据规模大。
另外的方法再补充。

3、hash的三种常用数据结构

数组、set、map， 见代码随想录

二、经典题目

1、242-有效的字母异位词-简单

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = “anagram”, t = “nagaram”
输出: true
s 和 t 仅包含小写字母
思路：hash, 而且因为只包含小写字母，一定范围的数据，适合用数组来表示hash。
最初是想用两个字母表分别计数，然后判断两个字母表的值是否相等； 优化思想是只用一个字母表，第一个字符串+1, 第二个字符串-1， 最后判断字母表的值是否都为0， 如此可以节省空间
分析：时间复杂度O(n); 空间O(1)
代码：

    bool isAnagram(string s, string t) {
        if(s.size() != t.size())
            return false;

        int count[26]  = {0};
        for(int i = 0; i < s.size(); i++){
            count[s[i] - 'a']++;
        }

        for(int i = 0; i < t.size(); i++){
            count[t[i] - 'a']--;
            if(count[t[i] - 'a'] < 0)
                return false;
        }
        
        // //判断count是否都为0
        // for(int i = 0; i < 26; i++){
        //     if(count[i] != 0)
        //         return false;
        // }
        return true;
        
        
    }
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

• 思路2： 将两个字符排序，然后遍历比较是否相等，空间O(1) 时间O(nlgn), 实现略

2、1002-查找公用字符-简单

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

示例 1：

输入：words = [“bella”,“label”,“roller”] 输出：[“e”,“l”,“l”] 示例 2：

输入：words = [“cool”,“lock”,“cook”] 输出：[“c”,“o”]

提示：

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

思路：统计出每个单词里里26个字符的出现的频率，然后取每个字符频率最小值，最后转成输出格式就可以了。
注意点：包括重复字符

class Solution {
public:

//注意空数组的判断，但在这里是>= 1的，可以省略
    vector<string> commonChars(vector<string>& words) {
        int hash[26] = {0};
        int record[26] = {0};
        vector<string> ans;
        //hash数组存储第一个单词的字符统计
        for(int i = 0; i < words[0].size(); i++){
            hash[words[0][i] - 'a']++;
        }
        
        for(int i = 1; i < words.size(); i++){
            memset(record, 0, 26 * sizeof(int));
            for(int j = 0; j < words[i].size(); j++){
                record[words[i][j] - 'a']++;
            }
            //取最小值
            for(int k = 0; k < 26; k++){
                hash[k] = min(hash[k], record[k]);
            }
        }
        string s; 
        for(int k = 0; k < 26; k++){
            while(hash[k] > 0){//注意重复字符！
                s = "";
                s.append(1, 'a' + k);
                ans.emplace_back(s);
                hash[k]--;
            }
        }
        return ans;
}
//错误思路：如果字符在一个单词中出现（无论几次），则hash+1，最后比较该字符出现次数是否等于单词数目;
//思路错误，因为包括重复字符！！！！！
};
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

3 、349-两个数组的交集-简单

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

思路：unordered_set结构的应用
刚开始想的还是用数组，因为有数值范围限制（0-1000）,若是这道题目没有限制数值的大小，或者哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。因为没有重复且不要求顺序，所以考虑用效率最高的unordered_map
注意点：1、for(auto & num : nums2)的写法
2、unordered_set的应用
分析： 时间和空间复杂度为O(m+n),m,n为nums1,2的长度

class Solution {
public:
//用unorder_set数据结构
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set(nums1.begin(), nums1.end());//直接用nums1赋值
        unordered_set<int> result_set;

        // for(int i = 0; i < nums2.size(); i++){
        //     if(set.find(nums2[i]) != set.end()){
        //         result.emplace_back(nums2[i]);

        //     }
        // }
        for(auto & num : nums2){//这里 num直接auto i : nums2 也可以，但无论是整型还是迭代器，使用引用都可以避免多余的拷贝步骤，节省时间开销
            if(set.find(num) != set.end()){
                result_set.insert(num);

            }
        }
        return vector<int>(result_set.begin(), result_set.end());
            
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4、202-快乐数-简单

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

思路1：判断一个元素是否在循环中，肯定想到用hash。非快乐数的判断，关键在于无限循环的判断，因为不知道循环的数值大小，所以用set
**注意点：**求一个数字的各位数的平方和的实现

代码：

class Solution {
public:
   
    //求一个数的各位数字的平方和
    int getPowSum(int n){
        int sum = 0;
        
        while(n){
            sum += pow(n%10 , 2);
            n = n /10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> record;
        while(n != 1){
            n = getPowSum(n);
            if(record.find(n) != record.end())
                return false;
            else
                record.insert(n);
        }

        return true;
    }
};
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

优化思路2： 使用 “快慢指针” 思想，找出循环：“快指针” 每次走两步，“慢指针” 每次走一步，当二者相等时，即为一个循环周期。此时，判断是不是因为 1 引起的循环，是的话就是快乐数，否则不是快乐数。
注意：此题不建议用集合记录每次的计算结果来判断是否进入循环，因为这个集合可能大到无法存储；另外，也不建议使用递归，同理，如果递归层次较深，会直接导致调用栈崩溃。不要因为这个题目给出的整数是 int 型而投机取巧。
该思路来自作者：linux-man， 参考链接

  
    bool isHappy(int n) {
        
        int slow , fast;
        slow = n;
        fast = getPowSum(n);
        while(fast != 1 && fast != slow){
            slow = getPowSum(slow);
            fast = getPowSum(fast);
            fast = getPowSum(fast);
        }
        return fast == 1; //两种情况，fast首先成为1， 或者循环相遇，
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

5、1-两数之和-简单

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

思路1：暴力搜索，双重循环， 时间O(n^2), 空间O(1)
思路2：利用map, key是 target - nums[i]， value为元素的下标i, 然后判断该数字是否在map中，即是否是一个targat的补集。

分析：时间空间都为O（n）

class Solution {
public:

    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        vector<int> result;
        for(int i = 0; i < nums.size(); i++){
            if(map.find(nums[i]) != map.end()){
                
                return {map[nums[i]], i};

            }else{
                int temp = target - nums[i];
                map[temp] = i;
            }
        }   
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

6、454-四数相加II-中等

三、总结

1、当我们遇到快速判断一个元素是否在集合中的场景，要想到用hash
2、小范围的数值，可以使用数组来做哈希的题目
2、如果题目没有限制数值的大小，或者哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费，考虑set
3、判断是否有循环，可以考虑 ”快慢指针“思想 ：“快指针” 每次走两步，“慢指针” 每次走一步，当二者相等时，即为一个循环周期，可节省空间。(见第4个例题）