Go语言题解LeetCode705设计哈希集合

目录
  • 题目描述
  • 思路分析
  • AC 代码

题目描述

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 <= 10^6
  • 最多调用 10^4 次 add、remove 和 contains

思路分析

实现使用了链地址法，解决哈希冲突方法使用了模取余的方法（较简单的）。

这里说下为什么大家说模最好取质数，我的理解是取质数可以让取余后的结果更加均匀，以减少冲突。

举个例子，假如我们取4为模，那么虽然理论上我们应该会让数字均匀落入4个桶中，但是对于下边这个数组：

1,3,5,7,9

所有数字都落入了1，3两个桶中，造成了极大的不均，导致哈希冲突发生频繁。对于一个合数，只要我们构造合数倍数相关的数组，就很容易使哈希冲突变多，所以尽量选用质数。

AC 代码

struct Listnode{
    int val;
    Listnode* next = nullptr;
    Listnode()=default;
    Listnode(int val){
        this->val = val;
    }
};
class MyHashSet {
public:
    /** Initialize your data structure here. */
    const int prime = 991;
    vector<Listnode*> nodes;
    MyHashSet(): nodes(prime, nullptr){
    }
    void add(int key) {
        if(nodes[key%prime] == nullptr){
            nodes[key%prime] = new Listnode(key);
        }else{
            Listnode* node = nodes[key%prime];
            while(node != nullptr){
                if(node->val == key)return;
                node = node->next;
            }
            node = new Listnode(key);
            node->next = nodes[key%prime];
            nodes[key%prime] = node;
        }
    }
    void remove(int key) {
        Listnode* prenode = nodes[key%prime];
        if(prenode != nullptr && prenode->val == key){
            if(prenode->next != nullptr){
                nodes[key%prime] = prenode->next;
                delete prenode;
            }else{
                delete prenode;
                nodes[key%prime] = nullptr;
            }
            return;
        }
        while(prenode != nullptr && prenode->next != nullptr){
            if(prenode->next->val == key){
                Listnode* temp = prenode->next;
                prenode->next = prenode->next->next;
                delete temp;
                return;
            }
            prenode = prenode->next;
        }
    }
    /** Returns true if this set contains the specif ied element */
    bool contains(int key) {
        Listnode* node = nodes[key%prime];
        while(node != nullptr){
            if(node->val == key)return true;
            node = node->next;
        }
        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);
 */

以上就是Go语言题解LeetCode705设计哈希集合的详细内容，更多关于Go语言设计哈希集合的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Go语言LeetCode题解706设计哈希映射

    目录 题目描述 思路分析 AC 代码 题目描述 706. 设计哈希映射 不使用任何内建的哈希表库设计一个哈希映射(HashMap). 实现 MyHashMap 类: MyHashMap() 用空映射初始化对象 void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) .如果 key 已经存在于映射中,则更新其对应的值 value . int get(int key) 返回特定的 key 所映射的 value :如果映射中不包含 key

  • Go语言题解LeetCode888公平糖果交换示例详解

    目录 一 描述 二 分析 三 答案 一 描述 888. 公平的糖果交换 - 力扣(LeetCode) (leetcode-cn.com) 爱丽丝和鲍勃拥有不同总数量的糖果.给你两个数组 aliceSizes 和 bobSizes ,aliceSizes[i] 是爱丽丝拥有的第 i 盒糖果中的糖果数量,bobSizes[j] 是鲍勃拥有的第 j 盒糖果中的糖果数量. 两人想要互相交换一盒糖果,这样在交换之后,他们就可以拥有相同总数量的糖果.一个人拥有的糖果总数量是他们每盒糖果数量的总和. 返回一个

  • Go语言LeetCode题解961在长度2N的数组中找出重复N次元素

    目录 题目描述 思路分析 AC 代码 题目描述 961. 在长度 2N 的数组中找出重复 N 次的元素 给你一个整数数组 nums ,该数组具有以下属性: nums.length == 2 * n. nums 包含 n + 1 个 不同的 元素 nums 中恰有一个元素重复 n 次 找出并返回重复了 n 次的那个元素. 示例 1: 输入:nums = [1,2,3,3] 输出:3 示例 2: 输入:nums = [2,1,2,5,3,2] 输出:2 示例 3: 输入:nums = [5,1,5,

  • go语言LeetCode题解720词典中最长的单词

    目录 一 描述 二 分析 三 答案 四 总结 一 描述 720. 词典中最长的单词 - 力扣(LeetCode) (leetcode-cn.com) 给出一个字符串数组 words 组成的一本英语词典.返回 words 中最长的一个单词,该单词是由 words 词典中其他单词逐步添加一个字母组成. 若其中有多个可行的答案,则返回答案中字典序最小的单词.若无答案,则返回空字符串. 示例 1: 输入:words = ["w","wo","wor",&

  • Go语言题解LeetCode724寻找数组的中心下标

    目录 题目描述 思路分析 AC 代码 题目描述 724. 寻找数组的中心下标 - 力扣(LeetCode) (leetcode-cn.com) 给你一个整数数组 nums ,请计算数组的 中心下标 . 数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和. 如果中心下标位于数组最左端,那么左侧数之和视为 0 ,因为在下标的左侧不存在元素.这一点对于中心下标位于数组最右端同样适用. 如果数组有多个中心下标,应该返回 最靠近左边 的那一个.如果数组不存在中心下标,返回 -

  • Go语言LeetCode题解937重新排列日志文件

    目录 一 题目描述 二 分析 三 答案 一 题目描述 937. 重新排列日志文件 - 力扣(LeetCode) (leetcode-cn.com) 给你一个日志数组 logs.每条日志都是以空格分隔的字串,其第一个字为字母与数字混合的 标识符 . 有两种不同类型的日志: 字母日志:除标识符之外,所有字均由小写字母组成 数字日志:除标识符之外,所有字均由数字组成 请按下述规则将日志重新排序: 所有 字母日志 都排在 数字日志 之前. 字母日志 在内容不同时,忽略标识符后,按内容字母顺序排序:在内容

  • Go语言leetcode题解953验证外星语词典示例详解

    目录 题目描述 思路分析 AC 代码 题目描述 953. 验证外星语词典 某种外星语也使用英文小写字母,但可能顺序 order 不同.字母表的顺序(order)是一些小写字母的排列. 给定一组用外星语书写的单词 words,以及其字母表的顺序 order,只有当给定的单词在这种外星语中按字典序排列时,返回 true:否则,返回 false. 示例 1: 输入:words = ["hello","leetcode"], order = "hlabcdefgi

  • Go语言题解LeetCode705设计哈希集合

    目录 题目描述 思路分析 AC 代码 题目描述 705. 设计哈希集合 不使用任何内建的哈希表库设计一个哈希集合(HashSet). 实现 MyHashSet 类: void add(key) 向哈希集合中插入值 key . bool contains(key) 返回哈希集合中是否存在这个值 key . void remove(key) 将给定值 key 从哈希集合中删除.如果哈希集合中没有这个值,什么也不做.   示例: 输入: ["MyHashSet", "add&quo

  • 分析Go语言接口的设计原则

    分析Go语言接口的设计原则

    目录 一.前言 二.开闭原则 三.依赖倒置原则 3.1.什么是依赖倒置原则 3.2.一个耦合度极高的模块关系设计 3.3.面向抽象层依赖倒转 一.前言 go的interface写起来更自由, 无需显示的实现, 只要实现了与interfece所包含的所有函数签名的相同的方法即可.让编码更灵活, 易扩展. 如何理解go语言中的interface呢? 1. interface是方法声明的集合 2.接口的方法与实现接口的类型方法格式一致 3.接口中所有方法均被实现 4. interface可以作为一种数

  • Go语言题解LeetCode268丢失的数字示例详解

    目录 题目描述 思路分析 AC 代码 异或两遍 - 丢失的数字 解题思路 代码 C++ 排序二分.加减法.异或 - 丢失的数字 解题思路: 题目描述 原题链接 : 268. 丢失的数字 给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数. 示例 1: 输入:nums = [3,0,1] 输出:2 解释:n = 3,因为有 3 个数字,所以所有的数字都在范围 [0,3] 内.2 是丢失的数字,因为它没有出现在 nums 中. 示例 2

  • go语言题解LeetCode506相对名次示例详解

    目录 一 描述 二 分析 三 答案 一 描述 506. 相对名次 给你一个长度为 n 的整数数组 score ,其中 score[i] 是第 i 位运动员在比赛中的得分.所有得分都 互不相同 . 运动员将根据得分 决定名次 ,其中名次第 1 的运动员得分最高,名次第 2 的运动员得分第 2 高,依此类推.运动员的名次决定了他们的获奖情况: 名次第 1 的运动员获金牌 "Gold Medal" . 名次第 2 的运动员获银牌 "Silver Medal" . 名次第

  • go语言题解LeetCode1128等价多米诺骨牌对的数量

    目录 题目描述 思路分析 AC 代码 偷懒解法 思路: 图解: 代码: 哈希表+元素转换 解题思路 代码 复杂度分析 题目描述 1128. 等价多米诺骨牌对的数量 - 力扣(LeetCode) 给你一个由一些多米诺骨牌组成的列表 dominoes. 如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌,我们就认为这两张牌是等价的. 形式上,dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a==c 且 b==d,或是 

  • go语言题解LeetCode1160拼写单词示例详解

    目录 题目描述 思路分析 AC 代码 别人用int[26] 解题思路 代码 c++几乎双百的哈希解法 代码 题目描述 1160. 拼写单词 - 力扣(LeetCode) 给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars. 假如你可以用 chars 中的『字母』(字符)拼写出 words 中的某个『单词』(字符串),那么我们就认为你掌握了这个单词. 注意:每次拼写(指拼写词汇表中的一个单词)时,chars 中的每个字母都只能用一次. 返回词汇表 words 中你

  • go语言题解LeetCode1275找出井字棋的获胜者示例

    目录 题目描述 思路分析 AC 代码 题目描述 1275. 找出井字棋的获胜者 - 力扣(LeetCode) A 和 B 在一个 3 x 3 的网格上玩井字棋. 井字棋游戏的规则如下: 玩家轮流将棋子放在空方格 (" ") 上. 第一个玩家 A 总是用 "X" 作为棋子,而第二个玩家 B 总是用 "O" 作为棋子. "X" 和 "O" 只能放在空方格中,而不能放在已经被占用的方格上. 只要有 3 个相同的(

  • go语言题解LeetCode88合并两个有序数组示例

    目录 题目描述 思路分析 AC 代码 题目描述 原题链接 : 88. 合并两个有序数组 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目. 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列. 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中.为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素

随机推荐