【LeetCode705】设计哈希集合(哈希)

简介: 0 <= key <= 10^6最多调用 104 次 add、remove 和 contains二、思路

一、题目

image.png

提示:


0 <= key <= 10^6

最多调用 104 次 add、remove 和 contains

二、思路

哈希表有个2个关键问题:


哈希函数:将任意值通过哈希函数映射到固定值,可以设哈希表的大小为b a s e basebase,输入哈希函数值为k e y keykey,设计一个简单的哈希函数:h a s h ( k e y ) = k e y m o d b a s e hash(key) = key \quad mod \quad basehash(key)=keymodbase。其中b a s e basebase一般取为质数,可以取987。

哈希表一般使用链地址法,即让每个vector元素是一个链表list。对哈希表的增删改查都是通过hash函数计算后,对这个list进行增删改查即可。

PS:


对vector<list<int>>a进行初始化大小时,如果是直接用vector<list<int>>a(987);是会报错的,可以定义后再用a.resize(987),但是这样是产生对象后才扩容到987,效率更快的写法是:MyHashSet():a(987){},即在构造a时就是987大小了。

在C++的STL中,map或者set可以直接使用find,但是vector或者list是不可以直接使用find的。

三、代码

class MyHashSet {
private:
    vector<list<int>>a;
    int base = 987;
    int hash(int key){
        return key % base;
    }
public:
    MyHashSet(){
        a.resize(987);
    }
    void add(int key) {
        int temp = hash(key);
        for(auto it = a[temp].begin(); it != a[temp].end(); it++){
            if(*it == key){
                return;
            }
        }
        a[temp].push_back(key);
    }
    void remove(int key) {
        int temp = hash(key);
        for(auto it = a[temp].begin(); it != a[temp].end(); it++){
            if(*it == key){
                //注意这里不能写成erase(key)
                a[temp].erase(it);
                return;
            }
        }
    }
    bool contains(int key) {
        int temp = hash(key);
        for(auto it = a[temp].begin(); it != a[temp].end(); it++){
            if(*it == key){
                return true;
            }
        }
        return false;
    }
};
/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */

image.png

相关文章
|
1月前
《LeetCode》—— 哈希
《LeetCode》—— 哈希
|
1月前
leetcode-1044:最长重复子串(滚动哈希)
leetcode-1044:最长重复子串(滚动哈希)
34 0
|
6天前
|
存储 SQL 算法
LeetCode 题目 87:递归\动态规划\哈希实现 扰乱字符串
LeetCode 题目 87:递归\动态规划\哈希实现 扰乱字符串
|
6天前
|
算法 数据挖掘 开发者
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
|
1月前
[leetcode] 705. 设计哈希集合
[leetcode] 705. 设计哈希集合
|
1月前
leetcode-1001:网格照明(自定义哈希集合)
leetcode-1001:网格照明(自定义哈希集合)
22 0
|
算法 索引
leetcode-每日一题745. 前缀和后缀搜索(哈希和字典树)
如果我们用前缀 prefix 和 后缀 suff去暴力对比所有单词肯定会超时,我们可以先把单词里所有的前缀后缀组合,中间用特殊符号@连接,对应的最大下标存入哈希表中。搜索时,用特殊符号@连接前缀后缀,在哈希表中进行搜索
69 0
leetcode-每日一题745. 前缀和后缀搜索(哈希和字典树)
|
算法
leetcode-每日一题873. 最长的斐波那契子序列的长度(哈希和二分)
题目要求斐波那契数列长度要大于等于3,就等于说要确定 x[1] 和 x[2]来确定x[3]…x[n]之和的数列,所以我们用两层for循环来枚举x[1] 和 x[2] ,因为斐波那契数列满足 x[i] = x[i - 1] + x[i - 2], 所以x[3] = x[1] + x[2] x[4] = x[3] + x[2]…,我们只需要三个变量来不断变换, 每次从 arr 中找前两个数,然后查看后续在符合斐波那契的数在arr中是否存在
83 0
leetcode-每日一题873. 最长的斐波那契子序列的长度(哈希和二分)
|
算法
leetcode-每日一题648. 单词替换(哈希)
将字符串数组中的所有字符串存入哈希表中,遍历sentence中的所有单词,从短到长遍历单词前缀,对比哈希表中的单词是否存在,存在则替换。
54 0
leetcode-每日一题648. 单词替换(哈希)
|
算法 容器
力扣17 - 电话号码的字母组合【回溯、哈希映射、队列】
对应力扣.17电话号码的字母组合,详细动画和图示讲解,带你快乐刷题
56 0
力扣17 - 电话号码的字母组合【回溯、哈希映射、队列】