首页 > 其他分享 >Day5||242.有效的字母异位词|349.两个数组的交集|202.快乐数|1.两数之和

Day5||242.有效的字母异位词|349.两个数组的交集|202.快乐数|1.两数之和

时间:2024-09-17 15:52:18浏览次数:12  
标签:std map 202 key nums Day5 set 哈希 两数

哈希表理论基础

哈希表(hash table):是根据关键码的值而直接进行范围的数据结构。

如数组也是一张哈希表。

 解决问题:一般哈希表都是用来快速判断一个元素是否出现集合里。(牺牲空间换取时间)

例如要查询一个名字是否在这所学校里。

要枚举的话时间复杂度是O(n),但如果使用哈希表的话, 只需要O(1)就可以做到。

我们只需要初始化把这所学校里学生的名字都存在哈希表里,在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

将学生姓名映射到哈希表上就涉及到了hash function ,也就是哈希函数

哈希函数,把学生的姓名直接映射为哈希表上的索引,然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。

哈希函数如下图所示,通过hashCode把名字转化为数值,一般hashcode是通过特定编码方式,可以将其他数据格式转化为不同的数值,这样就把学生名字映射为哈希表上的索引数字了。

 

哈希碰撞

如图所示,小李和小王都映射到了索引下标 1 的位置,这一现象叫做哈希碰撞

哈希表3

解决方法:

 1.拉链法:存储在链表上

2.线性探测法,一定要保证tablesize大于datasize。依靠哈希表中的空位来解决碰撞问题。

 

常见的三种哈希结构

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

在C++中,set 和 map 分别提供以下三种数据结构,其底层实现以及优劣如下表所示:

集合底层实现是否有序数值是否可以重复能否更改数值查询效率增删效率
std::set红黑树有序O(log n)O(log n)
std::multiset红黑树有序O(logn)O(logn)
std::unordered_set哈希表无序O(1)O(1)

std::unordered_set底层实现为哈希表,std::set 和std::multiset 的底层实现是红黑树,红黑树是一种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加。

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

std::unordered_map 底层实现为哈希表,std::map 和std::multimap 的底层实现是红黑树。同理,std::map 和std::multimap 的key也是有序的(这个问题也经常作为面试题,考察对语言容器底层的理解)。

当我们要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。

那么再来看一下map ,在map 是一个key value 的数据结构,map中,对key是有限制,对value没有限制的,因为key的存储方式使用红黑树实现的。

虽然std::set和std::multiset 的底层实现基于红黑树而非哈希表,它们通过红黑树来索引和存储数据。不过给我们的使用方式,还是哈希法的使用方式,即依靠键(key)来访问值(value)。所以使用这些数据结构来解决映射问题的方法,我们依然称之为哈希法。std::map也是一样的道理。

 242.有效的字母异位词

题目:242. 有效的字母异位词 - 力扣(LeetCode)

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

示例 1: 输入: s = "anagram", t = "nagaram" 输出: true

示例 2: 输入: s = "rat", t = "car" 输出: false

说明: 你可以假设字符串只包含小写字母。

可以用暴力解法,但要设置两次for循环外加记录重复的字母。

还有简单的方法就是把两个字符串重新排序,然后判断是否相等。

哈希表思路

定义一个record数组记录每个字母出现的次数就行了。record的大小可定义为26,因为字母a到z在ascll上是连续的数值,依次映射到索引下标是0-25。

然后进行两次遍历,遍历s时,字母所对应的下标元素加1;遍历t时,字母对应的下标元素-1。

最后检查下,如果record有的元素不为0的话,就是s和t的元素有多或少了的。如果record为0,那s和t就是字母异位词。

图解:

          代码

class Solution {
public:
    bool isAnagram(string s, string t) {
       int record[26]={0};
       for(int i=0;i<s.size();i++)//记录s中的元素
       {
        record[s[i]-'a']++;
       }

       for(int j=0;j<t.size();j++)
       {
        record[t[j]-'a']--;
       }
       for(int k=0;k<26;k++)
       {
        if(record[k]!=0)return false;
       }
       return true;
    }
};

 349.两个数组的交集

题目:349. 两个数组的交集 - 力扣(LeetCode)

题意:给定两个数组,编写一个函数来计算它们的交集。

349. 两个数组的交集

说明: 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。

思路:

用set做哈希表,存储nums1去重后的结果,然后nums2去重后和result比较,最后输出交集元素

代码:

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());//存储nums的元素(降重版)
     for(int num:nums2)//使用for循环遍历nums2的每一个num元素
     {
        if(nums_set.find(num)!=nums_set.end())//检查 nums_set 中是否存在 num。如果 num 在 nums_set 中找到了,find 函数返回一个迭代器指向 num,否则返回 nums_set.end()。
        {
            result_set.insert(num);//如果 num 存在于 nums_set 中,就将 num 插入到 result_set 中。这是因为 result_set 用来存储 nums1 和 nums2 的交集元素。
        }
     }
     return vector<int>(result_set.begin(),result_set.end());
//将 result_set 中的元素转换为 vector<int> 类型,并返回这个向量。result_set.begin() 和 result_set.end() 提供了构造 vector 的起始和结束迭代器。
    }
};

注意if(nums_set.find(num)!=nums_set.end()的含义

  • nums_set.find(num) 查找 num 是否在 nums_set 中。如果找到了,它返回一个迭代器,指向 num
  • nums_set.end() 返回一个迭代器,指向 nums_set 的末尾,即一个“无效”的位置,表示未找到 num
  • != nums_set.end() 这个比较检查 find 返回的迭代器是否不等于 end 迭代器。如果不等,说明 num 存在于 nums_set 中。

逻辑解释

  • 存在:如果 numnums_set 中,find 返回的迭代器会与 end 迭代器不同,此时条件 nums_set.find(num) != nums_set.end() 为真。
  • 不存在:如果 num 不在 nums_set 中,find 返回的迭代器与 end 迭代器相同,此时条件为假。

总之,这种用法的目的是检查一个元素是否存在于 unordered_set 中。如果存在,则执行相应的操作(在本例中是将元素插入到 result_set 中)。

202.快乐数 

题目:202. 快乐数 - 力扣(LeetCode)

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

「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为  1,那么这个数就是快乐数。

如果 n 是快乐数就返回 True ;不是,则返回 False 。

示例:

输入:19
输出:true
解释:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

思路

由于结果sum会无限循环变不到1,那么sum就有可能重复出现,判断sum是否会重复出现用到unordered_set,为了快速找到集合中的元素,我们就要考虑到用哈希表。如果sum重复出现了就返回false,否则找到1为止。

取个位数平方后求和---判断n是否是快乐数(判断sum是否为1和重复出现陷入循环)

代码

class Solution {
public:

    int getsum(int n)//获取每个个位数的平方和
    {
        int sum=0;
        while(n)
        {
        sum+=(n%10)*(n%10);
        n=n/10;;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int>set;
        while(1)
        {
            int sum=getsum(n);
            if(sum==1)return 1;//找到快乐数
            //如果find和set两个容器返回的值不相等证明sum重复出现过可能陷入无限循环了
            if(set.find(sum)!=set.end())
            return false;

            else 
            set.insert(sum);//否则就存进set哈希表中

            n=sum;//sum作为下一个数的计算
        }
    }
};

1.两数之和 

题目:1. 两数之和 - 力扣(LeetCode)

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

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

示例:

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

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

所以返回 [0, 1]

思路  

为什么会想到用哈希表?   

 为了查询一个元素是否出现过,或者是否在一个集合里

哈希表为什么用map

因为本题需要我们存放遍历过的元素及其下标,map里的key和value恰好适合。

而不用数组和set的原因是,数组空间是有限的如果元素太少哈希值太大就会浪费空间,而set只能存放一个数,而本题需要返回两个数的下标

本题map是用来存什么的

存放我们访问过的元素,这样遍历数组的过程就可以找到与当前元素相加为target的之前遍历过的元素和下标

map中的key和value用来存什么的

key:数组元素  value:数组元素对应的下标

补充:

C++中map,有三种类型:

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

如图 

 

代码

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 iter=map.find(target-nums[i]);//如果找到指定的键,find 返回一个指向该元素的迭代器。如果未找到,find 返回 map.end(),这是一个指向 map 末尾的迭代器,表示键不存在。
            if(iter!=map.end())return {iter->second,i};//找到匹配的数
            map.insert(pair<int,int>(nums[i],i));//没找到匹配的数,就把元素和下标存入map中
        }
        return {};
    }
};

知识点

1.

auto 关键字

  • auto 是一个类型推断关键字,用于自动推导变量的类型。编译器根据初始化表达式的类型来确定 auto 变量的实际类型。

  • 在这行代码中,auto 让编译器自动推导 iter 的类型为 std::unordered_map<int, int>::iterator。这种类型是 map.find(target - nums[i]) 方法返回的迭代器类型。

iter 变量

  • iter 是一个迭代器(iterator),用于访问 unordered_map 中的元素。在这行代码中,itermap.find(target - nums[i]) 方法返回的迭代器。

map.find(target - nums[i])

  • findunordered_map 提供的一个成员函数,用于查找指定键(在本例中是 target - nums[i])是否存在于 map 中。它返回一个迭代器:
    • 如果找到指定的键,find 返回一个指向该元素的迭代器。
    • 如果未找到,find 返回 map.end(),这是一个指向 map 末尾的迭代器,表示键不存在。

详细解释

  • 当你写 auto iter = map.find(target - nums[i]); 时,iter 被定义为 unordered_map<int, int>::iterator 类型。find 方法返回的迭代器可以用来检查键是否存在,并在存在时访问该元素的值。

  • iter 的用途

    • 如果 iter 不等于 map.end(),表示 map 中存在键 target - nums[i]。此时可以通过 iter->second 访问与该键关联的值。
    • 如果 iter 等于 map.end(),表示 target - nums[i] 不在 map 中。

 2.

pair 用于将两个不同类型的值组合在一起,形成一个二元组。每个 pair 由两个成员变量组成:firstsecond,分别代表组合的两个值。

pair 的定义

pair 的模板定义如下:


template <class T1, class T2> struct pair { T1 first; T2 second; // 构造函数和其他成员函数 };

  • T1T2pair 的两个类型参数。
  • firstpair 的第一个值,类型为 T1
  • secondpair 的第二个值,类型为 T2

在这行代码中

map.insert(pair<int, int>(nums[i], i));

  • pair<int, int>(nums[i], i):这里创建了一个 pair 对象,pair<int, int> 表示一个 pair 结构,其中第一个值是 int 类型(nums[i]),第二个值也是 int 类型(i)。即 pair<int, int>(nums[i], i) 创建了一个包含两个整数的 pair 对象,第一个整数是 nums[i],第二个整数是 i

  • map.insert(...)insertunordered_map 提供的一个成员函数,用于将一个 pair 对象插入到 unordered_map 中。unordered_map 是一个键值对集合,其中键(key)和对应的值(value)可以通过 pair 来表示。在这个例子中,pair<int, int>(nums[i], i) 被插入到 map 中,其中 nums[i] 作为键,i 作为值。

标签:std,map,202,key,nums,Day5,set,哈希,两数
From: https://blog.csdn.net/2301_79865280/article/details/142303099

相关文章

  • CS 61A Fall 2020 起步
    今天在曹大的知识星球立了一个flag,如下: 为什么会想到立这个flag呢?自己从本科的时候,就对计算机“感兴趣”,考研的时候选择了国内计算机名校的计算机专业,但是在读研期间写的代码并不多,没有从写代码中获得持续的正反馈。去年,我入职了一家国企,从事软件开发工作,刚入职的时候就开......
  • 2024.9.1_ChatGPT镜像列表
    收集自网络,更新于2024.9.1ChatGPT国内镜像ChatGPT外国镜像......
  • 2024-09-17-生活在Kubernetes中的Springboot
    Springboot和Kubernetes中的很多功能都是重叠的,SpringCloud重合的就更多了。不过我还是希望尽可能采用微服务及服务网格这套思路,应用层做轻,SpringCloud就不用了,重合的部分也尽可能用Kubernetes的功能。配置中心Kubernetes本身提供了对配置中心的支持,不需要再使用Apollo之类的工......
  • 水果软件21更新!Image-Line FL Studio Producer Edition v24.1.1.4285 WIN全插件版本+
    在数字音乐创作领域,FLStudio(也称为FruityLoops)一直以来都是众多音乐制作人心目中的首选工具。随着版本的不断更新迭代,FLStudioProducerEdition24.1.1.4285中文版的发布,无疑为广大的华语音乐创作者们带来了更为便捷、高效且功能强大的音乐制作体验。本文将从多个角度深入......
  • Docker 镜像加速列表(截止到20240910)
    国内经常使用Docker的朋友,可能都会涉及到配置镜像源的操作,来加速自己的镜像拉取。然而这段时间陆续发现曾经常用的国内镜像站(各种云商和高校镜像站)现在已经不能用了,搜索互联网可用镜像站或者镜像加速地址,并测试后汇总如下,使用前请自行斟酌。Docker镜像加速列表(截止到20240910)注......
  • leetCode2:两数相加(链表)
    题目:给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。请你将两个数相加,并以相同形式返回一个表示和的链表。你可以假设除了数字0之外,这两个数都不会以0开头。思路:遍历两个链表,逐位相加,还要加上进位结......
  • 2024第一学期 #9
    T1.P10136神秘人类智慧题。如果离散化后的\(n\le3\),那么答案即为\(\dfrac{mx\times(mx+1)}{2}\)。接下来考虑\(n\ge4\)的情况。应为鸽巢原理当\(a_i\bmodL\)只有三种不同的取值,所以必定有两个数\(i,j\)满足条件\(a_i\equiva_j\pmodL\)并且\(1\lei<......
  • 【数据分享】1975-2020年人口密度POP栅格数据
    数据来源GHS-POP空间栅格产品(GHS-POP_GLOBE_R2023)描绘了人口的分布,表示为每个单元的人数。这个数据集描述了人口的分布和密度,以每个单元的人数表示,1975年-2020年,五年间隔,空间分辨率1000m.官网下载地址:https://human-settlement.emergency.copernicus.eu/download.php?ds=po......
  • Origin Pro2024保姆级安装教程(附安装包)
    软件介绍OriginPro是一款功能强大的数据分析和制图软件,广泛应用于科学研究、工程分析、商业统计、生物医学等领域。支持多种数据格式,包括Excel、CSV、文本文件等,方便数据的导入和导出。同时提供数据清洗、转换、统计分析等功能,帮助用户提高数据质量,进行更深入的分析。具有较强......
  • 【数据分享】1985-2023年30米CLCD土地覆盖栅格数据分享
    1.数据来源​CLCD反映了中国快速的城市化进程和一系列生态工程,揭示了气候变化条件下人为对LC的影响,其在全球变化研究中具有潜在应用价值。2021年7月,武汉大学杨杰、黄昕两位教授共同撰写题为《30mannuallandcoveranditsdynamicsinChinafrom1990to2019》的研究论......