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近期发表的一篇报告中,团队从制度进步、产业生态、投融资形势、总结与展望四个方面对量子计…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
