当前位置：首页 > news >正文

哈希表day5

news 2025/6/6 22:31:14

242 有效的字母异位词

思路就是转为ASCII码，然后用一个数组记录26位字母出现的次数

#include <string>
class Solution{
public:bool isAnagram(string s,string t){int record[26]={0};for (int i=0;i<s.size();i++){record[s[i]-'a']++;}for (int i=0;i<t.size();i++){record[t[i]-'a']--;}for (int i=0;i<26;i++){if (record[i]!=0) return false;}return true;}
};

349 两个数组的交集

这部分学习到的知识就多了
1、std::unordered_set,这是一个C++容器，底层是哈希表，查询复杂度为O(1),其次，他不允许有重复的值(也就是说，将vector nums的值放进去，会自动去重)
2、如何将vector的东西放进unordered_set中呢？

unordered_set<int> num_set(nums1.begin(),nums1.end());

同理，将unordered_set中的东西放进到vector中

vector<int> result(unordered_set.begin(),unordered_set.end())

3、如何对unordered_set中的元素进行查找呢？
使用nums_set.find(num) 如果找到了，那么就返回一个指向该元素的迭代器，如果没找到，就返回nums_set.end()这个特殊的迭代器。

#include <vector>
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { //参数为nums1的引用，nums2的引用unordered_set<int> result_set;  //自动去重 + 查找速度快（平均 O(1)）unordered_set<int> nums_set(nums1.begin(),nums1.end());//构建一个新的unordered_set，把nums1放进nums_set中,使用的是迭代器的语法，从nums1的begin到nums1的endfor (int num:nums2){ //遍历 nums2 中的每一个数字 num。if (nums_set.find(num)!=nums_set.end()){    //如果nums_set.find(num)返回一个指向该元素的迭代器；如果没找到，那么就返回的是 nums_set.end()，这是一个“尾后迭代器”，表示“找不到”。result_set.insert(num); 
// 如果 num 存在于 nums_set 中：
// 返回一个 指向该元素的迭代器。
// 如果 num 不存在于 nums_set 中：
// 返回一个特殊的迭代器 —— nums_set.end()，表示“查找失败”或“无此元素”。}}return vector<int>(result_set.begin(),result_set.end()) //result_set.begin() 到 result_set.end() 形成一个范围，传给 vector 构造函数；}
};

202 快乐数

set.insert(num);
也就是将num加入到集合中

class Solution {
public:int getSum(int n){int result=0;while(n){result += (n%10)*(n%10);n = n/10;}return result;}bool isHappy(int n) {unordered_set<int> set;while(1){//不断循环int sum = getSum(n);if (sum==1){return true;}if (set.find(sum)!= set.end()){return false;}else{set.insert(sum);//新函数，将sum加入到set中}n = sum;}}
};