当前位置: 首页 > news >正文

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] = 1for n in nums2:if n in hashTable:result.append(n)hashTable.pop(n)  # 避免重复,将添加过的key删除掉return resultif __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] = 1else:hashTable[n] += 1for n in nums2:if n in hashTable:result.append(n)hashTable[n] -= 1if 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 resultif __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”上进行扩展;需要注意 当出现一次两个字符串交集为空时,直接返回结果,结束代码运行

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、字符串数组长度为1if 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# 将短字符串转化为dicthashTable = {}for ch in str1:if ch not in hashTable:hashTable[ch] = 1else:hashTable[ch] += 1# 遍历长字符串result = []for ch in str2:if ch in hashTable:result.append(ch)hashTable[ch] -= 1if 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)(二、数组交集问题)

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

[Mac软件]Adobe After Effects 2023 v23.5 中文苹果电脑版(支持M1)

After Effects是动画图形和视觉效果的行业标准。由运动设计师、平面设计师和视频编辑用于创建复杂的动画图形和视觉上吸引人的视频。 创建动画图形 使用预设样式为文本和图形添加动画效果,或逐帧调整它们。编辑、添加深度、制作动画或转换为可编辑的路径&#xff…...

范德波尔方程详细介绍与Python实现(附说明)

引言: 在研究真空管放大器的过程中,写下了一个振动微分方程。当时人们并没有混沌或是对初始条件敏感的概念。不过,当混沌理论有一定发展后,人们重新回顾这个方程时发现它其实是个混沌方程。当时,范德波尔在 Nature 杂志报告了基于这个微分方程的霓虹灯实验,发现当驱动信号…...

常用的GPT插件

0.简介 随着chatgpt爆火,这玩意并不对国内用户开放,如果想要使用的话还要需要进行翻墙以及国外手机号才能进行注册。 对于国内来说有很多国内免费的方法,这里就整理一下,方便大家开发 1. 网站类型 下面的网站无需注册即可免费…...

智慧校园用电安全解决方案

随着科技的不断发展,智慧校园建设逐渐成为了教育行业的一大趋势。在这个过程中,电力系统作为校园基础设施的重要组成部分,其安全、稳定、高效的运行显得尤为重要。下面小编来为大家介绍下智慧校园用电安全解决方案吧! 一、智慧校园电力系统现…...

【教程】DGL中的子图分区函数partition_graph讲解

转载请注明出处:小锋学长生活大爆炸[xfxuezhang.cn] 目录 函数形式 函数作用 函数内容 函数入参 函数返参 使用示例 实际上官方的函数解释中就已经非常详细了。 函数形式 def partition_graph(g, graph_name, num_parts, out_path, num_hops1, part…...

关于layui table回显以及选择下一页时记住上一页数据的问题

代码如下 <div class"layui-form-item"><label class"layui-form-label">选择商品</label><div class"layui-input-inline"><input type"text" name"keyword" id"keyword" placehold…...

kafka消息系统实战

kafka是什么&#xff1f; 是一种高吞吐量的、分布式、发布、订阅、消息系统 1.导入maven坐标 <dependency><groupId>org.apache.kafka</groupId><artifactId>kafka-clients</artifactId><version>2.4.1</version></dependency&…...

Kafka3.0.0版本——Leader故障处理细节原理

目录 一、服务器信息二、服务器基本信息及相关概念2.1、服务器基本信息2.2、LEO的概念2.3、HW的概念 三、Leader故障处理细节 一、服务器信息 三台服务器 原始服务器名称原始服务器ip节点centos7虚拟机1192.168.136.27broker0centos7虚拟机2192.168.136.28broker1centos7虚拟机…...

BI系统框架模型

一 技术架构 二 数据源 主数据 &#xff1a;组织|岗位|人员|大区|三大主数据&#xff08;客户、物料、供应商&#xff09;财务主数据&#xff08;科目|成本中心|利润中心|资产&#xff09;|工作中心|工艺路线 业务数据 &#xff1a;线索|业务机会|合同|订单|采购|生产|发…...

双向交错CCM图腾柱无桥单相PFC学习仿真与实现(3)硬件功能实现

前言 前面介绍了双向交错CCM图腾柱的系统设计仿真实现&#xff0c;仿真很理想 双向交错CCM图腾柱无桥单相PFC学习仿真与实现&#xff08;1&#xff09;系统问题分解_卡洛斯伊的博客-CSDN博客 然后又介绍了SOG锁相环仿真实现的原理 双向交错CCM图腾柱无桥单相PFC学习仿真与实…...

微软用 18 万行 Rust 重写了 Windows 内核

微软正在使用 Rust 编程语言重写其核心 Windows 库。 5 月 11 日——Azure 首席技术官 Mark Russinovich 表示&#xff0c;最新的 Windows 11 Insider Preview 版本是第一个包含内存安全编程语言 Rust 的版本。 “如果你参加了 Win11 Insider 环&#xff0c;你将在 Windows 内…...

word 调整列表缩进

word 调整列表缩进的一种方法&#xff0c;在试了其他方法无效后&#xff0c;按下图所示顺序处理&#xff0c;编号和文字之间的空白就没那么大了。 即右键word上方样式->点击修改格式->定义新编号格式->字体->取消勾选 “……对齐到网格”->确定...

nginx学习

一、nginx常用版本 Nginx开源版&#xff1a; http://nginx.org/ nginx plus商业版本&#xff08;好像功能支持更多&#xff09; https://www.nginx.com/ openresty &#xff08;免费&#xff0c;用的也是这个&#xff09; https://openresty.org/cn/ Tengine https://tengine.…...

python+TensorFlow实现人脸识别智能小程序的项目(包含TensorFlow版本与Pytorch版本)(一)

pythonTensorFlow实现人脸识别智能小程序的项目&#xff08;包含TensorFlow版本与Pytorch版本&#xff09;&#xff08;一&#xff09; 一&#xff1a;TensorFlow基础知识内容部分&#xff08;简明扼要&#xff0c;快速适应&#xff09;1、下载Cifar10数据集&#xff0c;并进行…...

ChatGPT怎么用于政府和公共服务?

将ChatGPT用于政府和公共服务领域是一种创新的应用方式&#xff0c;可以改善政府与公众之间的互动&#xff0c;提升公共服务的效率和质量。ChatGPT作为一个自然语言处理模型&#xff0c;可以在政府信息传递、公共参与、服务支持等方面发挥积极作用。以下将详细探讨ChatGPT如何用…...

dvwa文件上传通关及代码分析

文章目录 low等级medium等级high等级Impossible等级 low等级 查看源码&#xff1a; <?phpif( isset( $_POST[ Upload ] ) ) {// Where are we going to be writing to?$target_path DVWA_WEB_PAGE_TO_ROOT . "hackable/uploads/";$target_path . basename( …...

数字孪生:重塑政府决策与公共服务

在之前的文章中为大家分享了数字孪生在很多行业的应用场景&#xff0c;本文和大家一起探讨一下数字孪生在政务管理方面能有哪些应用&#xff0c;以及其对公共服务提供的积极影响。 1&#xff09;城市规划方面 数字孪生技术可用于模拟城市的发展和规划。政府可以建立城市的虚拟…...

Leetcode:【448. 找到所有数组中消失的数字】题解

题目 给你一个含 n 个整数的数组 nums &#xff0c;其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字&#xff0c;并以数组的形式返回结果。 难度&#xff1a;简单 题目链接&#xff1a;448. 找到所有数组中消失的数字 示例1 输入&…...

2023年中,量子计算产业现状——

2023年上半年&#xff0c;量子计算&#xff08;QC&#xff09;领域取得了一系列重要进展和突破&#xff0c;显示出量子计算技术的快速发展和商业应用的不断拓展。在iCV TAnk近期发表的一篇报告中&#xff0c;团队从制度进步、产业生态、投融资形势、总结与展望四个方面对量子计…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...