哈希表原理与 LeetCode 实战

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

1、数组

数组是最简单的哈希表形式。

2、set(集合)

C++ STL 中主要有 set, multiset, unordered_set。 unordered_set 的底层是哈希表，查询速率为 O(1)。

#include <iostream>
#include <unordered_set>
using namespace std;
int main(){
    unordered_set<int> uset;
    // 增
    uset.insert(3);
    // 删
    uset.erase(3);
    uset.clear();
    // 查
    int size = uset.size();
    bool isEmpty = uset.empty();
    for(auto it = uset.begin(); it!=uset.end(); ++it){
        cout<<*it<<endl;
    }
    for(int i:uset) cout<<i<<endl;
    return 0;
}

set 与 multiset 的底层实现是红黑树，查询速率是 O(log N)，不是哈希表实现。

3、map(映射)

主要分为 map, multimap, unordered_map。 unordered_map 底层同 unordered_set 一样是哈希表。

#include <iostream>
#include <unordered_map>
using namespace std;
int main(){
    // 默认构造
    unordered_map<int,int> umap;
    // 构造并初始化
    unordered_map<int,string> myMap1 = {{1,"one"},{2,"two"}};
    // 插入
    myMap1.insert({2,"2"});
    // 访问
    cout<<myMap1[2];
    // 删除
    myMap1.erase(2);
    // 查找元素
    auto it = myMap1.find(2);
    if(it!=myMap1.end()){
        cout<<"存在该元素"<<endl;
    }
    return 0;
}

map、multimap 底层都是红黑树结构。

基础练习

一、有效的字母异位词

给定两个字符串 s 和 t，判断 t 是否是 s 的字母异位词。

class Solution {
public:
    bool isAnagram(string s, string t) {
        int res[26]={0};
        for(char c:s) res[c-'a']++;
        for(char c:t) res[c-'a']--;
        for(int i:res) if(i!=0) return false;
        return true;
    }
};

二、两个数组的交集

返回两个数组的交集，输出结果中的每个元素一定是唯一的。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        int res1[1005]={},res2[1005]={};
        for(int i:nums1) res1[i]++;
        for(int i:nums2) res2[i]++;
        for(int i=0; i<1005; ++i){
            if(res1[i]!=0&&res2[i]!=0) res.push_back(i);
        }
        return res;
    }
};

三、快乐数

判断一个数 n 是不是快乐数。如果过程结果为 1，则是快乐数。

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> set;
        while(1){
            string str = to_string(n);
            n = 0;
            for(char c : str) n+=(int)pow(c-'0',2);
            if(n==1) return true;
            else{
                if(set.find(n)!=set.end()) return false;
                set.insert(n);
            }
        }
    }
};

四、两数之和

找出数组中和为目标值的两个整数，并返回它们的数组下标。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> umap;
        for(int i=0; i<nums.size(); ++i){
            int num = target-nums[i];
            auto it = umap.find(num);
            if(it!=umap.end()) return vector<int>{i,it->second};
            umap.insert({nums[i],i});
        }
        return vector<int>(0);
    }
};

五、四数相加 II

计算有多少个元组 (i, j, k, l) 使得 A[i] + B[j] + C[k] + D[l] = 0。

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int flag = 0;
        unordered_map<int,int> umap;
        for(int i:nums1){
            for(int j:nums2){
                umap[i+j]++;
            }
        }
        for(int i:nums3){
            for(int j:nums4){
                int num = -i-j;
                auto it = umap.find(num);
                if(it!=umap.end()) flag+=it->second;
            }
        }
        return flag;
    }
};

六、赎金信

判断 ransomNote 能不能由 magazine 里面的字符构成。

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int res[26]={0};
        for(char c:magazine){ res[c-'a']++; }
        for(char c:ransomNote){ res[c-'a']--; }
        for(int i:res){ if(i<0){ return false; } }
        return true;
    }
};

七、三数之和

返回所有和为 0 且不重复的三元组。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        for(int i=0; i<nums.size(); ++i){
            if(i>0&&nums[i]==nums[i-1]) continue;
            int sum = 0-nums[i];
            int l = i+1, r = nums.size()-1;
            while(l<r){
                if(l>i+1&&nums[l]==nums[l-1]){ l++; continue; }
                if(r<nums.size()-1 && nums[r+1]==nums[r]){ r--; continue; }
                if(nums[r]+nums[l]<sum){ l++; }
                else if(nums[r]+nums[l]>sum){ r--; }
                else{
                    res.push_back(vector<int>{nums[i],nums[l],nums[r]});
                    l++; r--;
                }
            }
        }
        return res;
    }
};

八、四数之和

找出满足条件且不重复的四元组。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        for(int i=0; i<nums.size(); ++i){
            if(i>0&&nums[i]==nums[i-1]) continue;
            for(int j=i+1; j<nums.size(); ++j){
                if(j>i+1&&nums[j-1]==nums[j]) continue;
                int l = j+1, r = nums.size()-1;
                long long sum = (long long)target-nums[i]-nums[j];
                while(l<r){
                    if(l>j+1&&nums[l-1]==nums[l]){ l++; continue; }
                    if(r<nums.size()-1&&nums[r+1]==nums[r]){ r--; continue; }
                    long long s_num = (long long)nums[r]+nums[l];
                    if(s_num>sum){ r--; continue; }
                    else if(s_num<sum){ l++; continue; }
                    else{
                        res.push_back(vector<int>{nums[i],nums[j],nums[l],nums[r]});
                        r--; l++;
                    }
                }
            }
        }
        return res;
    }
};

蓝桥真题

一、字符统计

给定一个只包含大写字母的字符串，输出其中出现次数最多的字符。 Java 版：

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int[] res = new int[26];
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();
        for (char c : str.toCharArray()) {
            res[c - 'A']++;
        }
        int maxNum = 0;
        for (int i : res) { maxNum = Math.max(maxNum, i); }
        for (int i = 0; i < 26; i++) {
            if (res[i] == maxNum) {
                System.out.print((char) (i + 'A'));
            }
        }
        scanner.close();
    }
}

C++ 版：

#include <iostream>
using namespace std;
int main() {
    int res[26]={0};
    string str;
    cin>>str;
    for(char c : str){ res[c-'A']++; }
    int max_num=0;
    for(int i:res) max_num = max(max_num,i);
    for(int i=0; i<26; ++i){
        if(res[i]==max_num) cout<<char(i+'A');
    }
    return 0;
}

二、连连看

寻找一对格子使得这两个格子中的整数相等，且它们的位置满足 |a-c|=|b-d|>0。 C++ 版：

#include <iostream>
using namespace std;
int arr[1005][1005],cur1[2005][1005],cur2[2005][1005];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> arr[i][j];
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            ans += cur1[i - j + 1000][arr[i][j]] + cur2[i + j][arr[i][j]];
            cur1[i - j + 1000][arr[i][j]]++;
            cur2[i + j][arr[i][j]]++;
        }
    }
    cout<<ans*2<<endl;
}

三、团建

计算两个人从各自树的根结点出发走向某个叶结点，路径上经过的所有结点上的权值构成的序列的最长公共前缀。 C++ 版：

#include <iostream>
#include <unordered_map>
#include <vector>
#define ll long long
const int num = 2e5+5;
ll n_arr[num];
ll m_arr[num];
using namespace std;
unordered_map<int,vector<int>> n_umap;
unordered_map<int,vector<int>> m_umap;
void dfs(int a, int b, int cur){
    if(n_arr[a]!=m_arr[b]) return;
    cur += 1;
    count = max(count,cur);
    for(int i=0; i<n_umap[a].size(); ++i){
        for(int j=0; j<m_umap[b].size(); ++j){
            dfs(n_umap[a][i],m_umap[b][j],cur);
        }
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; ++i) cin>>n_arr[i];
    for(int j=1; j<=m; ++j) cin>>m_arr[j];
    int l,r;
    for(int i=0; i<n-1; ++i){ cin>>l>>r; n_umap[l].push_back(r); }
    for(int i=0; i<m-1; ++i){ cin>>l>>r; m_umap[l].push_back(r); }
    dfs(1,1,0);
    cout<<count<<endl;
    return 0;
}

四、k 倍区间

计算有多少个区间 [i,j] 满足 Si,j 是 k 的非负整数倍。 C++ 版：

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    unordered_map<int,vector<ll>> umap;
    umap[0].push_back(-1);
    ll sum[n];
    int count = 0;
    int cur;
    for(int i=0; i<n; ++i){
        cin>>cur;
        if(i==0) sum[i] = cur;
        else sum[i] = sum[i-1] + cur;
        ll num = sum[i]%k;
        if(num<0) num+=k;
        vector<ll>& vec = umap[num];
        auto it = upper_bound(vec.begin(),vec.end(),sum[i]);
        count += it-vec.begin();
        vec.insert(it,sum[i]);
    }
    cout<<count;
    return 0;
}

知识点

1、multimap 如何查询值

本质上，这是一个非常简单的问题！

#include <iostream>
#include <map>
using namespace std;
int main(){
    multimap<int,int> mmap;
    mmap.insert({1,2});
    mmap.insert({1,3});
    mmap.insert({2,4});
    auto it = mmap.find(1);
    while(it!=mmap.end()&&it->first==1){
        cout<<it->first<<it->second<<endl;
        it++;
    }
    return 0;
}

2、vector 初始化-pair

vector<pair<int,int>> res{ pair<int,int>(1,1) };

3、库 upper_bound(二分查找的应用)

• 查找一个有序数列，并返回第一个大于某个数的位置！
• 可拓展性-cmp

#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;
bool cmp(int a,int b){ return a>b; }
int main(){
    vector<int> res{1,23,4,6,1,234};
    sort(res.begin(),res.end());
    auto it = upper_bound(res.begin(),res.end(),7);
    auto i = it-res.begin();
    cout<<i<<endl;
    return 0;
}

4、迭代器

迭代器提供了一种访问容器的方式。你可以把它看作一种特殊的指针，按照一定的顺序遍历容器中的元素。 常用操作：解引操作（*）、自增操作（++）、比较操作（!=、==）。

5、二分查找

• 基础 - 二分查找
• 变种 - 查找第一个/最后一个
• 变种 - 查找第一个大于的数字 upper_bound(...)

6、超集

一个集合中的每一个元素都在另一个集合中，并且后者可能包含前者没有的元素。

7、map 底层基本单位

std::map 是键值对的集合，每个元素的类型是 std::pair<const Key, T>。