哈希表笔记

教程来自代码随想录

哈希表笔记

什么时候使用哈希法：当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候

重点是在于如何转化查找的问题

有效的字母异位词

leetcode242
用对应++和–判断

bool isAnagram(string s, string t) {
        if(s.length()!=t.length()) return false;
        unordered_map<char,int> comp;
        for(int i=0;i<s.length();i++){
            comp[s[i]]++;
        }
        for(int i=0;i<t.length();i++){
            if(comp[t[i]])comp[t[i]]--;
            else return false;
        }

        return true;
    }

bool isAnagram(string s, string t) {
        int record[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
            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) {
                // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        // record数组所有元素都为零0，说明字符串s和t是字母异位词
        return true;
    }

赎金信（字母交集）

bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char,int> hashmap;
        for(char text:magazine){
            hashmap[text]++;
        }
        for(char need:ransomNote){
            if(hashmap[need])hashmap[need]--;
            else return false;
        }
        return true;
    }

两个数组交集

leetcode349

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> s1;
        unordered_set<int> num2(nums2.begin(),nums2.end());
        for(int i=0;i<nums1.size();i++){
            if(num2.find(nums1[i])!=num2.end()){
                s1.insert(nums1[i]);
            }
        }
        return vector<int>(s1.begin(),s1.end());
    }

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
        int hash[1005] = {0}; // 默认数值为0
        for (int num : nums1) { // nums1中出现的字母在hash数组中做记录
            hash[num] = 1;
        }
        for (int num : nums2) { // nums2中出现话，result记录
            if (hash[num] == 1) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }

快乐数（无限循环的本质是出现重复值）

unordered_set可以用来辅助查重

int getsum(int n){
        int sum=0;
        while(n){
            sum+=(n%10)*(n%10);
            n=(n-(n%10))/10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> repeat;

        while(1){
            int sum=getsum(n);
            if(sum==1)return true;
            else {
                n=sum;
                if(repeat.find(sum)!=repeat.end()){
                    return false;
                }
                repeat.insert(sum);
            }

        }
    }

查找数组中是否有两数之和等于目标值

可以查找target-num1

vector<int> twoSum(vector<int>& nums, int target) {
        int answer1,answer2;
        unordered_map<int,int> num;
        for(int i=0;i<nums.size();i++){
            auto iter=num.find(target-nums[i]); //find是找key
            if(iter!=num.end()){
                answer1=i;
                answer2=iter->second;
                break;
            }
            num[nums[i]]=i;
        }
        return vector<int>({answer1,answer2});
    }

四数相加

关键是组好key和value

int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        //关键点是想清楚key放什么,value放什么
        //key放a+b的值，value放值出现的次数
        unordered_map<int,int> hashmap;
        for(int a:nums1){
            for(int b:nums2){
                hashmap[a+b]++;
            }
        }

        int count=0;
        for(int c:nums3){
            for(int d:nums4){
                if(hashmap[0-c-d]){
                    count+=hashmap[0-c-d];
                }
            }
        }
        return count;
    }

查找出现k次的字符

作业题
给定一个ASCII字符串，查找字符串中，出现了k次的字符。比如，字符串"This is a good day!"中，出现了2次的字符为’a’,‘d’,‘i’,‘o’, ‘s’，出现了4次的字符为’ '。

INPUT
2
This is a good day! 2
This is a good day! 4
OUTPUT
'a','d','i','o','s'
' '

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include<queue>
#include <algorithm>

using namespace std;
struct Compare{
    bool operator()(char a,char b){
        return a>b;
    }
};
int main(){
    unordered_map<char,int> textset;

    int n;
    cin>>n;
    getchar();
    
    while(n--){
        int count;
        string s;
        getline(cin,s);
        //cout<<s<<endl;
        if(s[s.size()-1]>='0'&&s[s.size()-1]<='9'){
            count=s[s.size()-1]-'0'; 
            s=s.substr(0,s.size()-2);
        }else{
            continue;
        }

        unordered_map<char,int> hashmap;
        for(char ch:s){
            hashmap[ch]++;
        }

        //找k个，加入集里
        priority_queue<char,vector<char>,Compare> result;
        for(auto pair:hashmap){
            if(pair.second==count){
                result.push(pair.first);
            }
        }
        
        //打印
        if (!result.empty()) {
            while (!result.empty()) {
                char r=result.top();
                cout << '\'' << r << '\'';
                result.pop();
                if (!result.empty()) cout << ',';
            }
            cout << endl;
        } else {
            cout << endl;
        }
        
    }
}

有重复的元素查询（查询第k次出现的元素）

作业题
给出一个整数序列，请找出一个整数v的第k次出现（从左到右）在序列中的位置。为了增加题目的挑战性，请回答m个这样的查询。

INPUT
20 4
1 3 2 2 4 3 2 1 9 2 4 2 1 2 6 5 3 2 1 4
9 1
4 5
2 4
3 3
OUTPUT
9
0
10
17

哈希表用int-vector的格式
key是元素的值，vector存的是出现的所有位置

int main() {
    int n, m;
    while (cin >> n >> m) {
        unordered_map<int, vector<int>> hashmap;

        for (int i = 0; i < n; ++i) {
            int number;
            cin >> number;
            hashmap[number].push_back(i + 1); // Store position as 1-indexed
        }

        for (int i = 0; i < m; ++i) {
            int v, k;
            cin >> v >> k;
            auto it = hashmap.find(v);
            if (it != hashmap.end() && it->second.size() >= k) {
                cout << it->second[k - 1] << endl; // Convert back to 1-indexed
            } else {
                cout << "0" << endl;
            }
        }
    }
    return 0;
}