广西建设工程管理网站,网页设计与制作考试试题及答案,网站的动画效果代码大全,小程序制作开发如意推哈希表常用数据结构
查询一个元素是否出现过#xff0c;或者一个元素是否在集合里的时候#xff0c;就要第一时间想到哈希法。 哈希法也是空间换时间#xff0c;因为我们要使用额外的数组#xff0c;set或者是map来存放数据#xff0c;才能实现快速的查找。
集合底层实现…哈希表常用数据结构
查询一个元素是否出现过或者一个元素是否在集合里的时候就要第一时间想到哈希法。 哈希法也是空间换时间因为我们要使用额外的数组set或者是map来存放数据才能实现快速的查找。
集合底层实现key是否有序数值是否可以重复能否更改数值查询效率增删效率std::set红黑树有序否否O(log n)O(log n)std::multiset红黑树有序是否O(logn)O(logn)std::unordered_set哈希表无序否否O(1)O(1)
映射底层实现是否有序数值是否可以重复能否更改数值查询效率增删效率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)
一般使用unordered_set、unordered_map需要有序时使用set、map需要有序、重复时使用multiset、multimap
242.有效的字母异位词
给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的字母异位词。 注意若 s 和 t 中每个字符出现的次数都相同则称 s 和 t 互为字母异位词。
示例 1: 输入: s “anagram”, t “nagaram” 输出: true
示例 2: 输入: s “rat”, t “car” 输出: false
class Solution {
public:bool isAnagram(string s, string t) {int hashArr[26]{0};for(int i0;is.size();i){hashArr[s[i]-a];}for(int i0;it.size();i){hashArr[t[i]-a]--;}for(int i0;i26;i){if(hashArr[i]!0) return false;}return true;}
};383. 赎金信
给你两个字符串ransomNote 和 magazine 判断 ransomNote 能不能由 magazine 里面的字符构成。 如果可以返回 true 否则返回 false 。 magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1 输入ransomNote “a”, magazine “b” 输出false
示例 2 输入ransomNote “aa”, magazine “ab” 输出false
示例 3 输入ransomNote “aa”, magazine “aab” 输出true
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int hashArr[26] {0};// 将magazine中字符统计在哈希表中for(int i0;imagazine.size();i){hashArr[magazine[i]-a];}// for(int i0;iransomNote.size();i){hashArr[ransomNote[i]-a]--;}// 如果hash表出现负数说明magazine中字符不够ransomNote消耗for(int i0;i26;i){if(hashArr[i]0) return false;}return true;}
};349. 两个数组的交集
示例 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] 也是可通过的
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setint res;// 将nums1存入哈希表unordered_setint hashSet(nums1.begin(),nums1.end());// 遍历nums2在哈希表中查找nums2的元素for(int num:nums2){if(hashSet.find(num)!hashSet.end()){res.insert(num);}}return vectorint(res.begin(),res.end());}
};1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。
示例 1 输入nums [2,7,11,15], target 9 输出[0,1] 解释因为 nums[0] nums[1] 9 返回 [0, 1] 。
示例 2 输入nums [3,2,4], target 6 输出[1,2]
示例 3 输入nums [3,3], target 6 输出[0,1]
class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint,int map;for(int i0;inums.size();i){auto iter map.find(target-nums[i]);// 找到一对直接返回if(iter ! map.end()){return {iter-second,i};}// 插入到map中map.insert(pairint,int(nums[i],i));}return {};}
};
