代码随想录算法训练营第六天| 哈希表理论基础 242.有效的字母异位词 349. 两个数组的交集 202. 快乐数 1. 两数之和

y1158643600

1243人浏览 · 2024-07-22 17:23:00

y1158643600 · 2024-07-22 17:23:00 发布

一、哈希表理论基础

哈希表

哈希表（Hash Table）：根据关键码的值而直接进行访问的数据结构

一般通常选择数组下标或其他指标作为关键码，在使用时可以通过哈希函数快速定位到所要查找的数据位置

优点：查询速度快
缺点：空间效率低

哈希函数

哈希函数：所要查找的信息值与哈希表内关键码的一个映射。即通过哈希函数，可以用查找信息算出数组下标。

hash函数的构造方法

考虑因素：

执行速度(计算时间)
关键字长度
Hash Table的大小
关键字的分布情况
数据出现频率

主要构造方法：

直接定址法
数字分析法
平方取中法
折叠法
除留余数法
随机数法

存储位置冲突与解决办法

在使用哈希表时，通常会出现不同的两个数据算出相同的哈希表下标，此时存储就有了冲突。解决办法通常如下：

1. 开放定址法：

基本思想：有冲突时就去寻找下一个空的散列地址，只要表足够大，总能找到空的地址

2. 链地址法：

基本思想，相同散列地址的记录链成一单链表

在这里插入图片描述

常用的哈希结构

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

数组
set (集合)
map (映射)

C++ 容器类 <set>
set是基于平衡二叉搜索树 (通常是红黑树) 实现的一种集合型容器，满足集合的基本性质并有以下特性：

包含性：set中的元素是唯一的，不允许重复元素。
排序：元素自动按照升序排列，如果元素定义了自定义的比较函数，则按照比较函数的规则排序。

常用的操作如下:
insert(元素); //插入一个元素。
erase(元素); //删除一个元素。
find(元素); //查找一个元素。
size(); //返回容器中元素的数量。
empty(); //检查容器是否为空。

相比<set>，容器类<unoredered_set>结构相似，但不保证元素顺序，提供更快的增删改查操作。

C++ 容器类<map>
C++中的map是标准模板库（STL）中的一个关联容器，它存储了键值对（key-value pairs），其中每个键都是唯一的。map是基于平衡二叉搜索树，通常是红黑树实现的，容器中的元素按照键的比较关系自动排序。

简单来讲，map是一个带有名单的表格，表格里记录每个人的某项数据。与python的字典相似。

基本操作包括插入（insert）、查找（find）、删除（erase）、获取元素大小(size)、清空（clear）等。
//增加元素
map[1] = "apple"; //可以直接添加一个新的键值对，如果已经存在则会更新键值

二、LeetCode 242.有效的字母异位词

题目链接：242.有效的字母异位词

文章讲解：代码随想录
视频讲解：学透哈希表，数组使用有技巧！Leetcode：242.有效的字母异位词

思路

按照题意，需要判断两个单词里所含有的字母是否完全相同，使用哈希表存储判断即可。

C++代码

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length() != t.length()){
            return false;
        }
        vector<int> sl(26);
        vector<int> tl(26);
        for(auto& x: s){
            sl[x - 'a']++;
        }
        for(auto& y: t){
            tl[y - 'a']++;
        }
        if(sl == tl){
            return true;
        }
        else{
            return false;
        }
    }
};

三、LeetCode 349. 两个数组的交集

题目链接：349. 两个数组的交集

文章讲解：代码随想录
视频讲解：学透哈希表，set使用有技巧！Leetcode：349. 两个数组的交集

思路：

题目中两个要点：两个数组交集元素，即不重复的相同元素；以及不考虑返回顺序。基于这两个要点可以使用unordered_set，提取一个数组中的不重复元素并比较另一个数组即可。

C++代码

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> nums1_elem(nums1.begin(), nums1.end());
        unordered_set<int> inter;
        for(auto x: nums2){
            if(nums1_elem.find(x) != nums1_elem.end()){
                inter.insert(x);
            }
        }
        return vector<int>(inter.begin(), inter.end());
    }
};

Python代码

python本身自带的集合set支持与操作和交集函数，因此代码非常简单

补充：python语法set1 = set(list[])：从列表list创建集合set1

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

四、LeetCode 202. 快乐数

题目链接：202. 快乐数

文章讲解：代码随想录

思路：

用哈希表解决数学问题
该题目若不是在哈希表的章节里看到，直观上和哈希表关系一点没有。本题和我们小学见到过的一些数字计算小游戏、数字黑洞一类的问题有些像，我们可以对这个数学问题本身进行分析：

对于一个n位数字，我们按照题目要求的方式进行验证，可以作出三种可能的结果假设：

最终计算结果得到 $1$ ;
最终在一定数字范围内循环；
无限增大

对于第三种情况，一个 $n$ 位数字的范围即是 $100\sim999$ ，显然三位数进行每位平方并加和后的最大结果为 $9^{2}+9^{2}+9^{2}=243$ ，也就是说，所有三位数验证快乐数过程中的运算结果必定小于 $243$ ，若不能得到 $1$ 就会进入循环，因此第三种情况不会出现。

在这种情况下，则可以使用哈希表快速查找计算结果是否出现过，达到检验快乐数的目的。

C++代码

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> happy;
        while(true){
            int sum = 0;
            while (n) {
                sum += (n % 10) * (n % 10);
                n /= 10;
            }
            if(sum == 1){
                return true;
            }
            else{
                if(happy.find(sum) == happy.end()){
                    happy.insert(sum);
                    n = sum;
                }
                else{
                    return false;
                }
            }
        }
    }
};

五、LeetCode 1. 两数之和

题目链接：1. 两数之和

文章讲解：代码随想录
视频讲解：梦开始的地方，Leetcode：1.两数之和，学透哈希表，map使用有技巧！

思路：

本题使用复杂度 $O(n^{2})$ 的暴力算法可以得出正确结果，而使用哈希表可以使时间复杂度降至 $O (n)$ ，降复杂度的原因在于哈希表快速查询的特性简化了暴力算法中第二次遍历的操作;

题目不严格要求返回的下标顺序，因此可使用unordered_map来分别存放数组值key与下标值index；一次遍历的思路为，在访问到数组中一个元素时，在映射unordered_map中查询它对于target的补，若补存在，那么它们之和满足题目要求，返回两个数下标值；若补不存在，那么将当前访问到的数与其下标存入unordered_map。

C++代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        for(int i = 0; i < nums.size(); i++){
            auto it = map.find(target - nums[i]);
            if(it != map.end()){
                return {it->second, i};
            }
            else{
                map.insert({nums[i], i});
            }
        }
        return {};
    }
};