leetcode分类刷题:哈希表(Hash Table)(一、数组交集问题)

这篇具有很好参考价值的文章主要介绍了leetcode分类刷题:哈希表(Hash Table)(一、数组交集问题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1、当需要快速判断某元素是否出现在序列中时,就要用到哈希表了。
2、本文针对的总结题型为给定两个及多个数组,求解它们的交集。接下来,按照由浅入深层层递进的顺序总结以下几道题目。
3、以下题目需要共同注意的是:对于两个数组,我们总是尽量把短数组转换为哈希表,以减少后续在哈希表中的元素查找时间。

349. 两个数组的交集

简单要求:交集结果不考虑重复情况

from typing import List
'''
349. 两个数组的交集
给定两个数组 nums1 和 nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1:
    输入: nums1 = [1,2,2,1], nums2 = [2,2]
    输出: [2]
题眼:交集(快速判断元素是否出现在序列中)+输出结果每个元素唯一的,不考虑结果中的重复情况
思路1、哈希表用set(),将两个数组全部转换为哈希表
思路2、哈希表用dict(),将短数组转换为哈希表
'''


class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 思路1、哈希表用set()
        # nums1hash = set(nums1)  # 集合这种数据结构有点变态,直接去掉了重复元素,让遍历的计算量更小了
        # nums2hash = set(nums2)
        # result = []
        # for n in nums2hash:
        #     if n in nums1hash:
        #         result.append(n)
        # return result
        # 思路2、哈希表用dict()
        hashTable = {}
        result = []
        # 使得nums1指向短数组
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        # 将短数组转换为哈希表,以减少在哈希表中的元素查找时间
        for n in nums1:
            if n not in hashTable:
                hashTable[n] = 1
        for n in nums2:
            if n in hashTable:
                result.append(n)
                hashTable.pop(n)  # 避免重复,将添加过的key删除掉
        return result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')
            nums1 = [int(n) for n in in_line[1].split(']')[0].split('[')[1].split(',')]
            nums2 = [int(n) for n in in_line[2].split(']')[0].split('[')[1].split(',')]
            print(nums1)
            print(nums2)
            print(obj.intersection(nums1, nums2))
        except EOFError:
            break

350. 两个数组的交集 II

简单要求提升:交集结果需要考虑重复情况,在“349. 两个数组的交集”上进行扩展。

from typing import List
'''
350. 两个数组的交集 II
给你两个整数数组nums1 和 nums2 ,请你以数组形式返回两数组的交集。
返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可以不考虑输出结果的顺序。
示例 1:
    输入:nums1 = [1,2,2,1], nums2 = [2,2]
    输出:[2,2]
题眼:交集(快速判断元素是否出现在序列中)+输出结果每个元素按照最少的,考虑结果中的重复情况
思路2:两个数组全部转换成dict进行查找
'''


class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 思路1:在“349. 两个数组的交集”上进行扩展
        hashTable = {}
        result = []
        # 使得nums1指向短数组
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        # 将短数组转换为哈希表,以减少在哈希表中的元素查找时间
        for n in nums1:
            if n not in hashTable:
                hashTable[n] = 1
            else:
                hashTable[n] += 1
        for n in nums2:
            if n in hashTable:
                result.append(n)
                hashTable[n] -= 1
                if hashTable[n] == 0:  # 将添加完的key删除掉
                    hashTable.pop(n)
        return result

        # # 思路2:两个数组全部转换成dict进行查找
        # hashTable1, hashTable2 = {}, {}
        # result = []
        # # 使得nums1指向短数组
        # if len(nums1) > len(nums2):
        #     nums1, nums2 = nums2, nums1
        # # 先将两个数组转换为dict
        # for n in nums1:
        #     if n not in hashTable1:
        #         hashTable1[n] = 1
        #     else:
        #         hashTable1[n] += 1
        # for n in nums2:
        #     if n not in hashTable2:
        #         hashTable2[n] = 1
        #     else:
        #         hashTable2[n] += 1
        # # 对两个dict进行遍历,并添加存在交集时的最少元素
        # for key in hashTable2:
        #     if key in hashTable1:  # 在短数组的哈希表中检索,以减少在哈希表中的元素查找时间
        #         for _ in range(min(hashTable1[key], hashTable2[key])):
        #             result.append(key)
        # return result


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')
            in_line1 = in_line[1].split('[')[1].split(']')[0]
            nums1 = []
            if in_line1 != '':
                for n in in_line1.split(','):
                    nums1.append(int(n))
            in_line2 = in_line[2].split('[')[1].split(']')[0]
            nums2 = []
            if in_line2 != '':
                for n in in_line2.split(','):
                    nums2.append(int(n))
            print(obj.intersect(nums1, nums2))
        except EOFError:
            break

1002. 查找共用字符

简单要求继续提升:交集结果需要考虑重复情况,同时给定的数组为N个了,在“350. 两个数组的交集 II”上进行扩展;需要注意 当出现一次两个字符串交集为空时,直接返回结果,结束代码运行文章来源地址https://www.toymoban.com/news/detail-680216.html

from typing import List
'''
1002. 查找共用字符
给你一个字符串数组 words ,请你找出所有在 words 的每个字符串中都出现的共用字符( 包括重复字符),
并以数组形式返回。你可以按 任意顺序 返回答案。
示例 1:
    输入:words = ["bella","label","roller"]
    输出:["e","l","l"]
思路:“350. 两个数组的交集 II”的扩展题型,由两个数组找交集扩展到N个数组找交集
'''


class Solution:
    def commonChars(self, words: List[str]) -> List[str]:
        # 情况1、字符串数组长度为1
        if len(words) == 1:
            return []
        # 情况2、
        result = self.commmon(words[0], words[1])  # 先求两个字符串达到交集
        if result == '':  # 当出现一次两个字符串交集为空时,直接返回结果,结束代码运行
            return []
        for i in range(2, len(words)):  # 从第三个字符串开始比较
            result = self.commmon(result, words[i])
            if result == '':    # 当出现一次两个字符串交集为空时,直接返回结果,结束代码运行
                return []
        return list(result)

    # 返回两个字符串的交集,并将结果也设置为字符串:“350. 两个数组的交集 II”的实现过程
    def commmon(self, str1: str, str2: str) -> str:
        if len(str1) > len(str2):
            str1, str2 = str2, str1
        # 将短字符串转化为dict
        hashTable = {}
        for ch in str1:
            if ch not in hashTable:
                hashTable[ch] = 1
            else:
                hashTable[ch] += 1
        # 遍历长字符串
        result = []
        for ch in str2:
            if ch in hashTable:
                result.append(ch)
                hashTable[ch] -= 1
                if hashTable[ch] == 0:
                    hashTable.pop(ch)
        return ''.join(result)


if __name__ == "__main__":
    obj = Solution()
    while True:
        try:
            in_line = input().strip().split('=')[1].strip()[1: -1]
            words = []
            if in_line != '':
                for s in in_line.split(','):
                    words.append(s[1: -1])
            print(obj.commonChars(words))
        except EOFError:
            break

到了这里,关于leetcode分类刷题:哈希表(Hash Table)(一、数组交集问题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 两个数组的交集(力扣刷题)

            给定两个数组  nums1  和  nums2  ,返回  它们的交集  。输出结果中的每个元素一定是  唯一  的。我们可以  不考虑输出结果的顺序  。 来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/intersection-of-two-arrays   说明:  输出结果中的每个元素一定是唯一的。

    2023年04月09日
    浏览(43)
  • leetcode分类刷题:二分查找(Binary Search)(四、基于值域的数组/矩阵类型)

    基于值域的二分法与基于定义域的题型不同,它的目标是从一“ 特殊排序序列 ”中确定“第k个元素值”,而不像基于定义域的题型是从排序序列中找小于等于特定target值的第一个索引;同时,针对“特殊排序序列”,往往需要 嵌套使用双指针 法进行操作,进一步增加了对

    2024年02月11日
    浏览(61)
  • 数据结构与算法 | 哈希表(Hash Table)

    在二分搜索中提到了在有序集合中查询某个特定元素的时候,通过折半的方式进行搜索是一种很高效的算法。那能否根据特征直接定位元素,而非折半去查找?哈希表(Hash Table),也称为散列表,就是一种数据结构,用于实现键-值对的映射关系。它通过将键映射到特定的值

    2024年02月06日
    浏览(53)
  • 算法数据结构基础——哈希表(Hash Table)

    哈希表(Hash Table) :也叫做散列表。是根据关键码值(Key Value)直接进行访问的数据结构。 哈希表通过「键 key 」和「映射函数 Hash(key) 」计算出对应的「值 value 」,把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做「哈希函数(散列函数

    2024年02月13日
    浏览(44)
  • leetcode分类刷题:易混题辨析一、209. 长度最小的子数组 vs 560. 和为K的子数组

    1、刷题慢慢积累起来以后,遇到相似的题目时,会出现算法思路混淆了 2、这两道题都是对 连续子数组加和 进行考察,细节区别在于数组元素在209. 长度最小的子数组为 正整数(窗口增加元素递增,减少元素递减) ,在560. 和为K的子数组为 整数 3、209. 长度最小的子数组采

    2024年02月10日
    浏览(39)
  • 哈希表(Hash Table)-----运用实例【通过哈希表来管理雇员信息】(java详解) (✧∇✧)

    目录 一.哈希表简介: 实例介绍:  类的创建与说明: 各功能图示:  1.class HashTab{  };  2. class EmpLinkedList{ }; 3. class Emp{ }; 4.测试: 运行结果: 最后,完整代码: 哈希表(Hash Table):也叫做散列表。是 根据关键码值(Key Value)直接进行访问的数据结构。 哈希表通过「

    2024年02月20日
    浏览(39)
  • 【CMU 15-445】Extendible Hash Table 可扩展哈希详细理解

    最近在学习CMU的15-445 DB课程,在做Project1的Extendible Hash Table的时候,由于是先看了课程,过了一个多星期才做的Lab,对extendible hash table只能说是知道大体的意思,并没有透彻的了解它,尤其是bucket指针和数据重分配这一部分,涉及到比较tricky的位运算,在一知半解的情况下实

    2024年02月09日
    浏览(35)
  • leetcode&lintcode分类刷题:图论(三、多源最小距离问题)

    1、本次总结的题目通常是多个源头节点分别求解到达目标节点的最小距离,目标节点可能为多个,也可能为一个;要采用 广度优先搜索 的方法,但先提前入队的不是源头节点了,而是目标节点,由目标节点为基准一圈一圈的更新能够达到的“新目标”位置,每一圈更新能够

    2024年02月07日
    浏览(39)
  • Java学数据结构(4)——散列表Hash table & 散列函数 & 哈希冲突

    1.散列表,key,散列函数; 2.哈希冲突的解决; 3.string中的hashCode; 查找树ADT,它允许对元素的集合进行各种操作。本章讨论散列表(hash table)ADT,不过它只支持二叉查找树所允许的一部分操作。散列表的实现常常叫作散列(hashing)。散列是一种用于以常数平均时间执行插入、删除和

    2024年02月10日
    浏览(55)
  • day6 哈希 有效的字母异位词 两个数组的交集 快乐数 两数之和

    - day5周日休息 --- 哈希表 - 什么时候用     - 需要记录对比数据,判断数据是否在集合里面 - 哈希三种形式     1. 数组         - 记录一个数         - 已知长度,belike 26个字母         - 已知最大长度,且长度较小,belike 1 = num = 1000     2. set         - 记录一个数

    2024年02月16日
    浏览(66)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包