哈希表练习题(2024/5/29)

news/2024/9/25 8:53:15/

1有效的字母异位词

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

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= s.length, t.length <= 5 * 104
  • s 和 t 仅包含小写字母

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

  1. 计数器

    • 代码中的 record 数组就是一个哈希表,用于统计每个字母在字符串中出现的次数。
  2. 映射关系

    • 将字母映射到哈希表中的索引位置,通过字符与索引的对应关系,实现了字符出现次数的统计。
  3. 查找表

    • 在遍历第二个字符串时,通过哈希表快速查找并更新字符出现的次数。
  4. 返回结果

    • 最终,通过检查哈希表中每个元素是否为0,确定两个字符串是否为字母异位词。

代码:

class Solution {
public:// 判断两个字符串是否为字母异位词bool isAnagram(string s, string t) {// 记录字符出现次数的数组,初始值全部为0int record[26] = {0};// 遍历字符串s,更新字符出现次数for (int i = 0; i < s.size(); i++) {record[s[i] - 'a']++;}// 遍历字符串t,更新字符出现次数for (int i = 0; i < t.size(); i++) {record[t[i] - 'a']--;}// 检查所有字符出现次数是否均为0,若不是则返回falsefor (int i = 0; i < 26; i++) {if (record[i] != 0) {return false;}}// 所有字符出现次数均为0,返回truereturn true;}
};

2两个数组的交集

给定两个数组 nums1 和 nums2 ,返回 它们的 

交集

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

示例 1:

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

示例 2:

输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
解释:[4,9] 也是可通过的

提示:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

思路:

   输出结果中的每个元素一定是唯一的,也就是说输出的结果的去重的, 同时可以不考虑输出结果的顺序    要用到哈希数据结构:unordered_set 

  1. 创建集合

    • 首先创建一个用于存储结果的无序集合 result_set,以及将第一个数组 nums1 转化为无序集合 nums_set,方便进行快速查找。
  2. 查找交集

    • 遍历第二个数组 nums2 中的每个元素,在 nums_set 中查找是否存在相同元素,若存在则将其加入结果集合 result_set 中。
  3. 返回结果

    • 最后将结果集合转化为数组并返回。

代码:

class Solution {
public:// 求两个数组的交集vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {// 用于存储结果的无序集合unordered_set<int> result_set; // 创建一个无序集合来存储结果// 将 nums1 转化为无序集合,方便进行查找unordered_set<int> nums_set(nums1.begin(), nums1.end()); // 将 nums1 转化为无序集合// 遍历 nums2,查找是否存在于 nums1 中,存在则加入结果集合for (int num : nums2) { // 遍历 nums2 中的每个元素if (nums_set.find(num) != nums_set.end()) { // 查找当前元素是否在 nums1 中result_set.insert(num); // 如果在,将当前元素加入结果集合}}// 将结果集合转化为数组并返回return vector<int>(result_set.begin(), result_set.end()); // 将结果集合转化为数组并返回}
};


http://www.ppmy.cn/news/1464383.html

相关文章

【Linux进程篇】Linux进程管理——进程创建与终止

W...Y的主页 &#x1f60a; 代码仓库分享&#x1f495; 目录 进程创建 fork函数初识 写时拷贝 fork常规用法 fork调用失败的原因 进程终止 进程退出场景 _exit函数 exit函数 return退出 进程创建 fork函数初识 在linux中fork函数时非常重要的函数&#xff0c;它从已…

现代操作系统上创建各类链接的方法汇总

文章目录 现代操作系统上创建各类链接的方法汇总windows: cmd下的mklink创建链接示例 powershell 创建链接创建常规文件和目录创建链接 linux shell 创建硬链接NAMESYNOPSIS详细说明常用选项示例 检查与辨识符号链接&#x1f388;linux下检查ls -l 命令file 命令 windows下检查…

【SPSS】基于因子分析法对水果茶调查问卷进行分析

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…

Hive 变量定义与引用

文章目录 1.背景2.Hive 变量命名空间查看变量设置变量引用变量 参考文献 1.背景 在书写 Hive SQL 时&#xff0c;有时需要将重复出现的值从 SQL 分离出来&#xff0c;以变量的方式表示和引用。 设置变量和引用变量可以带来以下几个好处&#xff1a; 简化查询语句&#xff1a;…

设计模式——职责链(责任链)模式

目录 职责链模式 小俱求实习 结构图 实例 职责链模式优点 职责链模式缺点 使用场景 1.springmvc流程 ​2.mybatis的执行流程 3.spring的过滤器和拦截器 职责链模式 使多个对象都有机会处理请求&#xff0c;从而避免请求的发送者和接受者之间的耦合关系。将这个对象连成…

F. Longest Strike[双指针详解]

Longest Strike 题面翻译 给你一个长度为 n n n 的序列 a a a 和一个整数 k k k&#xff0c;你要求一个区间 [ l , r ] [l,r] [l,r] 满足&#xff1a; 对于任何整数 x ∈ [ l , r ] x∈[l,r] x∈[l,r]&#xff0c; x x x 在 a a a 中的出现次数不少于 k k k 次。最大…

去掉macOS终端命令行前的(base)

macOS在安装了Anaconda&#xff08;或miniconda&#xff09;后&#xff0c;每次打开terminal都会默认打开名为base的虚拟环境。 默认不启动base conda config --set auto_activate_base false默认启动base conda config --set auto_activate_base true

JRT性能演示

演示视频 君生我未生&#xff0c;我生君已老&#xff0c;这里是java信创频道JRT&#xff0c;真信创-不糊弄。 基础架构决定上层建筑&#xff0c;和给有些品种的植物种植一样&#xff0c;品种不对&#xff0c;施肥浇水再多&#xff0c;也是不可能长成参天大树的。JRT吸收了各方…