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是动画图形和视觉效果的行业标准。由运动设计师、平面设计师和视频编辑用于创建复杂的动画图形和视觉上吸引人的视频。 创建动画图形 使用预设样式为文本和图形添加动画效果,或逐帧调整它们。编辑、添加深度、制作动画或转换为可编辑的路径ÿ…...
范德波尔方程详细介绍与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是什么? 是一种高吞吐量的、分布式、发布、订阅、消息系统 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系统框架模型
一 技术架构 二 数据源 主数据 :组织|岗位|人员|大区|三大主数据(客户、物料、供应商)财务主数据(科目|成本中心|利润中心|资产)|工作中心|工艺路线 业务数据 :线索|业务机会|合同|订单|采购|生产|发…...
双向交错CCM图腾柱无桥单相PFC学习仿真与实现(3)硬件功能实现
前言 前面介绍了双向交错CCM图腾柱的系统设计仿真实现,仿真很理想 双向交错CCM图腾柱无桥单相PFC学习仿真与实现(1)系统问题分解_卡洛斯伊的博客-CSDN博客 然后又介绍了SOG锁相环仿真实现的原理 双向交错CCM图腾柱无桥单相PFC学习仿真与实…...
微软用 18 万行 Rust 重写了 Windows 内核
微软正在使用 Rust 编程语言重写其核心 Windows 库。 5 月 11 日——Azure 首席技术官 Mark Russinovich 表示,最新的 Windows 11 Insider Preview 版本是第一个包含内存安全编程语言 Rust 的版本。 “如果你参加了 Win11 Insider 环,你将在 Windows 内…...
word 调整列表缩进
word 调整列表缩进的一种方法,在试了其他方法无效后,按下图所示顺序处理,编号和文字之间的空白就没那么大了。 即右键word上方样式->点击修改格式->定义新编号格式->字体->取消勾选 “……对齐到网格”->确定...
nginx学习
一、nginx常用版本 Nginx开源版: http://nginx.org/ nginx plus商业版本(好像功能支持更多) https://www.nginx.com/ openresty (免费,用的也是这个) https://openresty.org/cn/ Tengine https://tengine.…...
python+TensorFlow实现人脸识别智能小程序的项目(包含TensorFlow版本与Pytorch版本)(一)
pythonTensorFlow实现人脸识别智能小程序的项目(包含TensorFlow版本与Pytorch版本)(一) 一:TensorFlow基础知识内容部分(简明扼要,快速适应)1、下载Cifar10数据集,并进行…...
ChatGPT怎么用于政府和公共服务?
将ChatGPT用于政府和公共服务领域是一种创新的应用方式,可以改善政府与公众之间的互动,提升公共服务的效率和质量。ChatGPT作为一个自然语言处理模型,可以在政府信息传递、公共参与、服务支持等方面发挥积极作用。以下将详细探讨ChatGPT如何用…...
dvwa文件上传通关及代码分析
文章目录 low等级medium等级high等级Impossible等级 low等级 查看源码: <?phpif( isset( $_POST[ Upload ] ) ) {// Where are we going to be writing to?$target_path DVWA_WEB_PAGE_TO_ROOT . "hackable/uploads/";$target_path . basename( …...
数字孪生:重塑政府决策与公共服务
在之前的文章中为大家分享了数字孪生在很多行业的应用场景,本文和大家一起探讨一下数字孪生在政务管理方面能有哪些应用,以及其对公共服务提供的积极影响。 1)城市规划方面 数字孪生技术可用于模拟城市的发展和规划。政府可以建立城市的虚拟…...
Leetcode:【448. 找到所有数组中消失的数字】题解
题目 给你一个含 n 个整数的数组 nums ,其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字,并以数组的形式返回结果。 难度:简单 题目链接:448. 找到所有数组中消失的数字 示例1 输入&…...
2023年中,量子计算产业现状——
2023年上半年,量子计算(QC)领域取得了一系列重要进展和突破,显示出量子计算技术的快速发展和商业应用的不断拓展。在iCV TAnk近期发表的一篇报告中,团队从制度进步、产业生态、投融资形势、总结与展望四个方面对量子计…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...
STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...
