初学python记录:力扣705. 设计哈希集合

这篇具有很好参考价值的文章主要介绍了初学python记录:力扣705. 设计哈希集合。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目:

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

实现 MyHashSet 类:

  • void add(key) 向哈希集合中插入值 key 。
  • bool contains(key) 返回哈希集合中是否存在这个值 key 。
  • void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值,什么也不做。

提示:

  • 0 <= key <= 10^6
  • 最多调用 104 次 addremove 和 contains

思考:

偷懒做法:超大数组

因为 0<= key <= 10^6,所以可以建立一个长度为 10^6 + 1 的超大数组,数组的索引代表key值,数组的值(True / False)代表是否存在key值。代码如下:

class MyHashSet(object):

    def __init__(self):
        self.hashset =  [False] * 1000001


    def add(self, key):
        """
        :type key: int
        :rtype: None
        """
        self.hashset[key] = True


    def remove(self, key):
        """
        :type key: int
        :rtype: None
        """
        self.hashset[key] = False


    def contains(self, key):
        """
        :type key: int
        :rtype: bool
        """
        return self.hashset[key]

提交通过:

初学python记录:力扣705. 设计哈希集合,哈希算法,leetcode,算法,python 

正经做法:哈希函数+链地址法

设置一个长度为volume的数组hash,由volume个空列表组成。哈希函数为index=key%volume。那么对于任意值key,用哈希函数计算得到key所在的列表的位置,然后在列表中进行add、remove、contains操作。

由于 0<= key <= 10^6,所以取volume值为10^3,代码如下:

class MyHashSet(object):

    def __init__(self):
        self.volume = 1000
        self.hashset = [[] for _ in range(self.volume)]


    def _hash(self, key):
        return key % self.volume    # 哈希函数


    def add(self, key):
        """
        :type key: int
        :rtype: None
        """
        index = self._hash(key)
        if key not in self.hashset[index]:
            self.hashset[index].append(key)


    def remove(self, key):
        """
        :type key: int
        :rtype: None
        """
        index = self._hash(key)
        if key in self.hashset[index]:
            self.hashset[index].remove(key)


    def contains(self, key):
        """
        :type key: int
        :rtype: bool
        """
        index = self._hash(key)
        if key in self.hashset[index]:
            return True
        return False

提交通过:

初学python记录:力扣705. 设计哈希集合,哈希算法,leetcode,算法,python 

 文章来源地址https://www.toymoban.com/news/detail-851929.html

到了这里,关于初学python记录:力扣705. 设计哈希集合的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法思考记录】【前缀和,C++】力扣1277. 统计全为 1 的正方形子矩阵

    原题链接 题目要求我们统计在一个由0和1构成的矩阵中,所有完全由1组成的正方形子矩阵的数量。这是一道中等难度的算法题目,其关键在于高效地计算出不同大小的正方形子矩阵是否完全由1组成。 解决此问题的一个有效方法是使用 前缀和 算法。前缀和是一种预处理技术

    2024年02月03日
    浏览(39)
  • 哈希表:给定一组查找关键字(32,15,7,11,4,28,56,61,79),哈希表长为m=12,请按照除留余数法设计一个哈希函数,设每个记录的查找概率相等。

    慕课数据结构题目: 给定一组查找(32,15,7,11,4,28,56,61,79),哈希表长为m=12,请按照除留余数法设计一个哈希函数,设每个记录的查找概率相等。 (1)画出按照 线性探测 再散列处理冲突得到的哈希表(给出求解过程),并计算等概率情况下查找成功和查找失败时的平均

    2024年02月11日
    浏览(55)
  • Hash(哈希)算法-Python实现

    哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值,这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母,随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的

    2023年04月15日
    浏览(36)
  • 【数据结构与算法】哈希表设计(C\C++)

    针对某个集体中人名设计一个哈希表,使得平均查找长度不超过R,并完成相应的建表和查找程序。 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造。用伪随机探测再散列法处理冲突。 取读者周围

    2024年02月04日
    浏览(54)
  • Python小知识 - 一致性哈希算法

    一致性哈希算法 一致性哈希算法(Consistent Hashing Algorithm)是用于解决分布式系统中节点增减比较频繁的问题。它的思想是,将数据映射到0~2^64-1的哈希空间中,并通过哈希函数对数据进行映射,计算出数据所在的节点。当节点增加或减少时,只需要重新计算数据所在的节点即

    2024年02月09日
    浏览(51)
  • 【Python查找算法】二分查找、线性查找、哈希查找

    目录 1 二分查找算法  2 线性查找算法 3 哈希查找算法         二分查找(Binary Search)是一种用于在有序数据集合中查找特定元素的高效算法。它的工作原理基于将数据集合分成两半,然后逐步缩小搜索范围,直到找到目标元素或确定目标元素不存在。 以下是二分查找的

    2024年02月08日
    浏览(52)
  • 哈希-力扣01两数之和

    给定一个整数数组  nums  和一个整数目标值  target ,请你在该数组中找出  和为目标值  target   的那  两个  整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1:

    2024年01月20日
    浏览(42)
  • 力扣-哈希-最长连续序列

    给定一个未排序的整数数组  nums  ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。 请你设计并实现时间复杂度为  O(n)  的算法解决此问题。 示例 1: **输入:**nums = [100,4,200,1,3,2] **输出:**4 **解释:**最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

    2024年02月10日
    浏览(33)
  • 【力扣】202. 快乐数 <哈希>

    编写一个算法来判断一个数 n 是不是快乐数。 【快乐数】 定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1,那么这个数就是快乐数。 如果 n 是

    2024年02月11日
    浏览(38)
  • 二刷力扣--哈希表

    哈希表可以根据键在O(1)时间内进行访问。 哈希表实际上可以看成是一个数组,但是可以通过哈希函数计算出数组下标,直接访问。 常用的有集合 set() ,字典 dict() 。 #字典 给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。 注意 :若 s 和 t 中每个字符

    2024年02月07日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包