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近期发表的一篇报告中,团队从制度进步、产业生态、投融资形势、总结与展望四个方面对量子计…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
莫兰迪高级灰总结计划简约商务通用PPT模版
莫兰迪高级灰总结计划简约商务通用PPT模版,莫兰迪调色板清新简约工作汇报PPT模版,莫兰迪时尚风极简设计PPT模版,大学生毕业论文答辩PPT模版,莫兰迪配色总结计划简约商务通用PPT模版,莫兰迪商务汇报PPT模版,…...
力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...
