[leetcode] 705. 设计哈希集合

简介: [leetcode] 705. 设计哈希集合

不使用任何内建的哈希表库设计一个哈希集合(HashSet)。


实现 MyHashSet 类:


void add(key) 向哈希集合中插入值 key 。

bool contains(key) 返回哈希集合中是否存在这个值 key 。

void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值,什么也不做。


示例:


输入:

[“MyHashSet”, “add”, “add”, “contains”, “contains”, “add”, “contains”, “remove”, “contains”]

[[], [1], [2], [1], [3], [2], [2], [2], [2]]

输出:

[null, null, null, true, false, null, true, null, false]


解释:

MyHashSet myHashSet = new MyHashSet();

myHashSet.add(1); // set = [1]

myHashSet.add(2); // set = [1, 2]

myHashSet.contains(1); // 返回 True

myHashSet.contains(3); // 返回 False ,(未找到)

myHashSet.add(2); // set = [1, 2]

myHashSet.contains(2); // 返回 True

myHashSet.remove(2); // set = [1]

myHashSet.contains(2); // 返回 False ,(已移除)


提示:


0 <= key <= 106

最多调用 104 次 add、remove 和 contains


class MyHashSet {
    private static final int BASE = 769;
    private LinkedList[] data;

    /** Initialize your data structure here. */
    public MyHashSet() {
        data = new LinkedList[BASE];
        for (int i = 0; i < BASE; ++i) {
            data[i] = new LinkedList<Integer>();
        }
    }
    
    public void add(int key) {
        int h = hash(key);
        if (!data[h].contains(key)) {
            data[h].offerLast(key);
        }
        return;
    }
    
    public void remove(int key) {
        int h = hash(key);
        if (data[h].contains(key)) {
            data[h].remove(Integer.valueOf(key));
        }
    }
    
    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        int h = hash(key);
        return data[h].contains(key);
    }

    private static int hash(int key) {
        return key % BASE;
    }
}
相关文章
|
1月前
《LeetCode》—— 哈希
《LeetCode》—— 哈希
|
1月前
leetcode-1044:最长重复子串(滚动哈希)
leetcode-1044:最长重复子串(滚动哈希)
37 0
|
12天前
|
算法 数据挖掘 开发者
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
|
11天前
|
存储 SQL 算法
LeetCode 题目 87:递归\动态规划\哈希实现 扰乱字符串
LeetCode 题目 87:递归\动态规划\哈希实现 扰乱字符串
|
1月前
leetcode-1001:网格照明(自定义哈希集合)
leetcode-1001:网格照明(自定义哈希集合)
23 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中是否存在
85 0
leetcode-每日一题873. 最长的斐波那契子序列的长度(哈希和二分)
|
算法
leetcode-每日一题648. 单词替换(哈希)
将字符串数组中的所有字符串存入哈希表中,遍历sentence中的所有单词,从短到长遍历单词前缀,对比哈希表中的单词是否存在,存在则替换。
56 0
leetcode-每日一题648. 单词替换(哈希)
|
算法 容器
力扣17 - 电话号码的字母组合【回溯、哈希映射、队列】
对应力扣.17电话号码的字母组合,详细动画和图示讲解,带你快乐刷题
57 0
力扣17 - 电话号码的字母组合【回溯、哈希映射、队列】
|
7天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题