LeetCode题练习与总结:两个列表的最小索引总和--599
一、题目描述
假设 Andy 和 Doris 想在晚餐时选择一家餐厅,并且他们都有一个表示最喜爱餐厅的列表,每个餐厅的名字用字符串表示。
你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个,则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。
示例 1:
输入: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"],list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"] 输出: ["Shogun"] 解释: 他们唯一共同喜爱的餐厅是“Shogun”。
示例 2:
输入:list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"],list2 = ["KFC", "Shogun", "Burger King"] 输出: ["Shogun"] 解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”,它有最小的索引和1(0+1)。
提示:
1 <= list1.length, list2.length <= 1000
1 <= list1[i].length, list2[i].length <= 30
list1[i]
和list2[i]
由空格' '
和英文字母组成。list1
的所有字符串都是 唯一 的。list2
中的所有字符串都是 唯一 的。
二、解题思路
-
首先,我们需要一个数据结构来存储每个餐厅名字及其在两个列表中的索引。这里我们可以使用一个哈希表(HashMap)。
-
遍历第一个列表
list1
,将每个餐厅的名字和它的索引存入哈希表中。 -
接着,遍历第二个列表
list2
,对于每个餐厅名字,检查它是否在哈希表中存在,如果存在,则计算索引和(该餐厅在list1
中的索引加上在list2
中的索引)。 -
我们需要找到最小的索引和,因此我们可以维护一个变量来记录当前的最小索引和,并在遍历过程中更新它。
-
如果找到一个更小的索引和,我们就更新结果列表;如果找到一个与当前最小索引和相同的索引和,则将该餐厅添加到结果列表中。
-
最后,返回结果列表。
三、具体代码
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;public class Solution {public String[] findRestaurant(String[] list1, String[] list2) {// 使用HashMap存储list1中餐厅的名字和对应的索引Map<String, Integer> indexMap = new HashMap<>();for (int i = 0; i < list1.length; i++) {indexMap.put(list1[i], i);}// 初始化最小索引和为最大可能值int minSum = Integer.MAX_VALUE;// 使用List来存储结果List<String> result = new ArrayList<>();// 遍历list2for (int i = 0; i < list2.length; i++) {if (indexMap.containsKey(list2[i])) {int sum = i + indexMap.get(list2[i]); // 计算索引和// 如果找到更小的索引和,则更新结果列表和最小索引和if (sum < minSum) {result.clear();result.add(list2[i]);minSum = sum;} else if (sum == minSum) { // 如果索引和相同,则添加到结果列表result.add(list2[i]);}}}// 将结果列表转换为数组并返回return result.toArray(new String[0]);}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
-
第一个
for
循环遍历list1
数组,其长度为n
(假设list1
的长度为n
),这个循环的时间复杂度是O(n)。 -
第二个
for
循环遍历list2
数组,其长度为m
(假设list2
的长度为m
),这个循环的时间复杂度是O(m)。 -
在第二个循环中,我们调用了
containsKey
方法,这是一个常数时间操作,其时间复杂度是O(1)。 -
add
和clear
方法在ArrayList
中的时间复杂度都是O(1)。
综上所述,总的时间复杂度是O(n + m),因为两个循环是独立的,我们只需将它们的时间复杂度相加。
2. 空间复杂度
-
indexMap
是一个哈希表,用于存储list1
中所有餐厅名字及其索引。在最坏的情况下,如果list1
中的每个元素都是唯一的,那么indexMap
将包含n
个条目。因此,空间复杂度是O(n)。 -
result
是一个列表,用于存储共同喜爱的餐厅。在最坏的情况下,如果list1
和list2
完全相同,那么result
将包含所有n
个餐厅。因此,空间复杂度是O(n)。
综上所述,总的空间复杂度是O(n),因为indexMap
和result
是独立的数据结构,且indexMap
占据了主要的存储空间。
五、总结知识点
-
类定义:
public class Solution
:定义了一个公共类Solution
。
-
方法定义:
public String[] findRestaurant(String[] list1, String[] list2)
:定义了一个公共方法findRestaurant
,它接受两个字符串数组作为参数,并返回一个字符串数组。
-
数据结构:
HashMap<String, Integer>
:使用哈希表来存储键值对,其中键是字符串(餐厅名字),值是整数(索引)。ArrayList<String>
:使用动态数组来存储结果列表。
-
循环:
for
循环:用于遍历数组。
-
哈希表操作:
put
:将键值对存入哈希表。containsKey
:检查哈希表中是否包含指定的键。get
:根据键获取哈希表中的值。
-
数组与列表转换:
toArray
:将列表转换为数组。
-
条件语句:
if
:用于条件判断。else if
:用于处理多个条件分支。
-
变量操作:
- 变量赋值:例如
minSum = sum;
。 - 变量比较:例如
if (sum < minSum)
。
- 变量赋值:例如
-
常量:
Integer.MAX_VALUE
:Java中定义的整型最大值常量。
-
集合操作:
clear
:清空列表中的所有元素。add
:向列表中添加元素。
-
返回值:
return
:用于从方法中返回值。
以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。
相关文章:
LeetCode题练习与总结:两个列表的最小索引总和--599
一、题目描述 假设 Andy 和 Doris 想在晚餐时选择一家餐厅,并且他们都有一个表示最喜爱餐厅的列表,每个餐厅的名字用字符串表示。 你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个,则输出所有答案并且不考虑顺序。…...
IBM数据与人工智能系列 安装 IBM 编程助手
登录CPD环境 ${CPDM_OC_LOGIN} 安装编程助手 cpd-cli manage apply-olm \ --release${VERSION} \ --cpd_operator_ns${PROJECT_CPD_INST_OPERATORS} \ --componentswca cpd-cli manage apply-cr \ --componentswca \ --release${VERSION} \ --cpd_instance_ns${PROJECT_CPD…...
细说机器学习算法之ROC曲线用于模型评估
系列文章目录 第一章:Pyhton机器学习算法之KNN 第二章:Pyhton机器学习算法之K—Means 第三章:Pyhton机器学习算法之随机森林 第四章:Pyhton机器学习算法之线性回归 第五章:Pyhton机器学习算法之有监督学习与无监督…...
unity学习25:用 transform 进行旋转和移动,简单的太阳地球月亮模型,以及父子级关系
目录 备注内容 1游戏物体的父子级关系 1.1 父子物体 1.2 坐标关系 1.3 父子物体实际是用 每个gameobject的tranform来关联的 2 获取gameObject的静态数据 2.1 具体命令 2.2 具体代码 2.3 输出结果 3 获取gameObject 的方向 3.1 游戏里默认的3个方向 3.2 获取方向代…...
如何利用天赋实现最大化的价值输出
这种文章,以我现在的实力很难写出来。所以需要引用一些视频。 上92高校容易吗 如果基于天赋努力,非常容易。 如果不是这样,非常非常难。 高考失败人生完蛋?复读考上交大,进入社会才发现学历只是一张纸,98…...
使用 postman 测试思源笔记接口
思源笔记 API 权鉴 官方文档-中文:https://github.com/siyuan-note/siyuan/blob/master/API_zh_CN.md 权鉴相关介绍截图: 对应的xxx,在软件中查看 如上图:在每次发送 API 请求时,需要在 Header 中添加 以下键值对&a…...
代码随想录33
目录 leetcode738.单调递增的字符串 优化过的算法: 困难模式:968.监控二叉树 leetcode738.单调递增的字符串 当且仅当每个相邻位数上的数字 x 和 y 满足 x < y 时,我们称这个整数是单调递增的。 给定一个整数 n ,返回 小于…...
解决Oracle SQL语句性能问题(10.5)——常用Hint及语法(7)(其他Hint)
10.5.3. 常用hint 10.5.3.7. 其他Hint 1)cardinality:显式的指示优化器为SQL语句的某个行源指定势。该Hint具体语法如下所示。 SQL> select /*+ cardinality([@qb] [table] card ) */ ...; --注: 1)这里,第一个参数(@qb)为可选参数,指定查询语句块名;第二个参数…...
FFmpeg(7.1版本)的基本组成
1. 前言 FFmpeg 是一个非常流行的开源项目,它提供了处理音频、视频以及其他多媒体内容的强大工具。FFmpeg 包含了大量的库,可以用来解码、编码、转码、处理和播放几乎所有类型的多媒体文件。它广泛用于视频和音频的录制、转换、流媒体传输等领域。 2. FFmpeg的组成 1. FFmp…...
Hypium+python鸿蒙原生自动化安装配置
Hypiumpython自动化搭建 文章目录 Python安装pip源配置HDC安装Hypium安装DevEco Testing Hypium插件安装及使用方法插件安装工程创建区域 Python安装 推荐从官网获取3.10版本,其他版本可能出现兼容性问题 Python下载地址 下载64/32bitwindows安装文件&am…...
文明的基因:在传承中破茧重生
敦煌莫高窟的壁画历经千年风雨,至今仍在向世界讲述着东方美学的密码。那些斑驳的壁画上,既有北魏时期的天竺梵音,也留存着盛唐气象的长安余韵。文明的基因从未停止生长,就像莫高窟的壁画师们在临摹前朝壁画时,总会在衣…...
因果推断与机器学习—用机器学习解决因果推断问题
Judea Pearl 将当前备受瞩目的机器学习研究戏谑地称为“仅限于曲线拟合”,然而,曲线拟合的实现绝非易事。机器学习模型在图像识别、语音识别、自然语言处理、蛋白质分子结构预测以及搜索推荐等多个领域均展现出显著的应用效果。 在因果推断任务中,在完成因果效应识别之后,需…...
笔试-二进制
应用题 将符合区间[l,r]内的十进制整数转换为二进制表示,请问不包含“101”的整数个数是多少? 实现 l int(input("请输入下限l,其值大于等于1:")) r int(input("请输入上限r,其值大于等于l&#x…...
Day52:range()函数
在 Python 中,range() 是一个内置函数,用于生成一系列数字,通常用于循环结构中。它非常适合用于生成指定范围内的整数序列,并且支持步长控制,常用于 for 循环中。 今天我们将学习如何使用 range() 函数,并…...
数据结构:栈篇
ps: 本文所有图均为博主亲手所画,本文所有代码基于vs2022实现 系列文章目录 数据结构初探: 顺序表 数据结构初探:链表之单链表篇 数据结构初探:链表之双向链表篇 链表特别篇:链表经典算法问题 文章目录 系列文章目录前言一.栈的概念及其结构1.1概念1.2结构 二.准备工作1.Stack…...
药店药品销售管理系统的设计与实现
标题:药店药品销售管理系统的设计与实现 内容:1.摘要 摘要:本文介绍了药店药品销售管理系统的设计与实现。该系统旨在提高药店的运营效率和管理水平,通过信息化手段实现药品销售、库存管理、财务管理等功能。本文详细阐述了系统的需求分析、设计思路、技…...
【AI论文】VideoAuteur:迈向长叙事视频
摘要:近期的视频生成模型在制作持续数秒的高质量视频片段方面已展现出令人鼓舞的成果。然而,这些模型在生成能传达清晰且富有信息量的长序列时面临挑战,限制了它们支持连贯叙事的能力。在本文中,我们提出了一个大规模烹饪视频数据…...
pytorch基于FastText实现词嵌入
FastText 是 Facebook AI Research 提出的 改进版 Word2Vec,可以: ✅ 利用 n-grams 处理未登录词 比 Word2Vec 更快、更准确 适用于中文等形态丰富的语言 完整的 PyTorch FastText 代码(基于中文语料),包含࿱…...
PyTorch API 详细中文文档,基于PyTorch2.5
PyTorch API 详细中文文档 按模块分类,涵盖核心函数与用法示例 目录 张量操作 (Tensor Operations)数学运算 (Math Operations)自动求导 (Autograd)神经网络模块 (torch.nn)优化器 (torch.optim)数据加载与处理 (torch.utils.data)设备管理 (Device Management)模…...
leetcode 2300. 咒语和药水的成功对数
题目如下 数据范围 示例 注意到n和m的长度最长达到10的5次方所以时间复杂度为n方的必然超时。 因为题目要求我们返回每个位置的spell对应的有效对数所以我们只需要找到第一个有效的药水就行,这里可以先对potions排序随后使用二分查找把时间复杂度压到nlogn就不会…...
C# 实现 “Hello World” 教程
.NET学习资料 .NET学习资料 .NET学习资料 C# 作为一种广泛应用于.NET 开发的编程语言,以其简洁、高效和类型安全等特性,深受开发者喜爱。在踏入 C# 编程领域时,编写经典的 “Hello World” 程序是重要的起点,它能帮助我们快速熟…...
Elasticsearch——Elasticsearch性能优化实战
摘要 本文主要介绍了 Elasticsearch 性能优化的实战方法,从硬件配置优化、索引优化设置、查询方面优化、数据结构优化以及集群架构设计等五个方面进行了详细阐述,旨在帮助读者提升 Elasticsearch 的性能表现。 1. 硬件配置优化 升级硬件设备配置一直都…...
CentOS 7 搭建lsyncd实现文件实时同步 —— 筑梦之路
在 CentOS 7 上搭建 lsyncd(Live Syncing Daemon)以实现文件的实时同步,可以按照以下步骤进行操作。lsyncd 是一个基于 inotify 的轻量级实时同步工具,支持本地和远程同步。以下是详细的安装和配置步骤: 1. 系统准备 …...
pytorch实现变分自编码器
人工智能例子汇总:AI常见的算法和例子-CSDN博客 变分自编码器(Variational Autoencoder, VAE)是一种生成模型,属于深度学习中的无监督学习方法。它通过学习输入数据的潜在分布(Latent Distribution)&…...
【数据结构】初识链表
顺序表的优缺点 缺点: 中间/头部的插入删除,时间复杂度效率较低,为O(N) 空间不够的时候需要扩容。 如果是异地扩容,增容需要申请新空间,拷贝数据,释放旧空间,会有不小的消耗。 扩容可能会存在…...
【llm对话系统】大模型 Llama 源码分析之并行训练方案
1. 引言 训练大型语言模型 (LLM) 需要巨大的计算资源和内存。为了高效地训练这些模型,我们需要采用各种并行策略,将计算和数据分布到多个 GPU 或设备上。Llama 作为当前最流行的开源大模型之一,其训练代码中采用了多种并行技术。本文将深入 …...
S4 HANA税码科目确定(OB40)
本文主要介绍在S4 HANA OP中税码科目确定(OB40)相关设置。具体请参照如下内容: 税码科目确定(OB40) 在以上界面维护“Transaction Key”的记账码。 在以上界面进一步维护“Transaction Key”确定科目的规则。 Chart of Account:用于明确该规则适用于什么科目表。 …...
Mysql的主从复制及扩展功能
一、配置过程 1.配置master vim /etc/my.cnf [mysqld] datadir/data/mysql 指定数据库文件的存储位置 socket/data/mysql/mysql.sock symbolic-links0 log-binmysql-bin 启用二进制日志,用于记录数据库的更…...
C#,入门教程(10)——常量、变量与命名规则的基础知识
上一篇: C#,入门教程(09)——运算符的基础知识https://blog.csdn.net/beijinghorn/article/details/123908269 C#用于保存计算数据的元素,称为“变量”。 其中一般不改变初值的变量,称为常变量,简称“常量”。 无论…...
ideal的maven使用(两种方法)
方法一: 1.建立一个maven项目 2.像上一篇博客,重新配置一下maven即可 方法二:模块和项目选项一样:...
doris:导入时实现数据转换
Doris 在数据导入时提供了强大的数据转换能力,可以简化部分数据处理流程,减少对额外 ETL 工具的依赖。主要支持以下四种转换方式: 列映射:将源数据列映射到目标表的不同列。 列变换:使用函数和表达式对源数据进行实时…...
开源智慧园区管理系统对比五款主流产品探索智能运营新模式
内容概要 在这个数字化迅速发展的时代,园区管理也迎来了全新的机遇和挑战。众所周知,开源智慧园区管理系统作为一种创新解决方案,正逐步打破传统管理的局限性。它的开放性不仅使得系统可以根据具体需求进行灵活调整,也为用户提供…...
ARM内核:嵌入式时代的核心引擎
引言 在当今智能设备无处不在的时代,ARM(Advanced RISC Machines)处理器凭借其高性能、低功耗的特性,成为智能手机、物联网设备、汽车电子等领域的核心引擎。作为精简指令集(RISC)的典范,ARM核…...
ITS290F Human Computer Interaction
ITS290F Human Computer Interaction & User Experience Design Lab 1. Introduction to CodePen What you’ll learn in this lab: • Understanding CodePen • Creating a front-end page • Using Google form to submit your lab work CodePen is a cloud-based in…...
[Java]继承
1. 什么是继承? 继承是面向对象编程的一种机制,允许一个类(叫做子类)继承另一个类(叫做父类)的属性和方法。也就是说,子类可以“继承”父类的行为(方法)和状态ÿ…...
DeepSeek能下围棋吗?(续)
休息了一下,接着琢磨围棋,其实前面一篇里的规则有个漏洞的,就是邻居关系定义有问题,先回顾一下游戏规则: 游戏规则 定义: 1.数字对,是指两个1到9之间的整数组成的有序集合。可与记为(m,n)&…...
51单片机(STC89C52)开发:点亮一个小灯
软件安装: 安装开发板CH340驱动。 安装KEILC51开发软件:C51V901.exe。 下载软件:PZ-ISP.exe 创建项目: 新建main.c 将main.c加入至项目中: main.c:点亮一个小灯 #include "reg52.h"sbit LED1P2^0; //P2的…...
【数据结构】并查集
1.基本操作 void makeset(){ for(int i1;i<n;i)fa[i]i; }int findd(int x){ while(fa[x]!x)xfa[x]fa[fa[x]]; return x; }void unionn(int x,int y){ int zxfindd(x);int zyfindd(y); if(zx!zy)fa[zy]zx; }2.种类并查集 Parity Game 关押罪犯 [NOIP 2010 提高组] 关押罪…...
基于Rectified Flow FLUX的图像编辑方法 RF-Solver
Diffusion Models专栏文章汇总:入门与实战 前言:现在越来越多的开源模型是基于Rectified Flow,特别是FLUX和HunYuan Video,但是Rectified Flow inversion的性质和之前有所不同,这篇博客解读一下如何使用Rectified Flow对FLUX进行编辑。 目录 RF直接逆向会出现问题 为什R…...
[创业之路-269]:《创业讨论会》- 系统之韵:从麻雀到5G系统的共通性探索
关键词: 从系统的角度,麻雀、人体系统、企业系统、软硬件系统、软件系统、通信系统、5G系统是类似的: 都有:内在看不见的规律、外在显性各种现象 都是:输入、处理、输出 都是:静态、要素、组成、结构、组织…...
C语言指针专题三 -- 指针数组
目录 1. 指针数组的核心原理 2. 指针数组与二维数组的区别 3. 编程实例 4. 常见陷阱与防御 5. 总结 1. 指针数组的核心原理 指针数组是一种特殊数组,其所有元素均为指针类型。每个元素存储一个内存地址,可指向不同类型的数据(通常指向同…...
Contrastive Imitation Learning
机器人模仿学习中对比解码的一致性采样 摘要 本文中,我们在机器人应用的对比模仿学习中,利用一致性采样来挖掘演示质量中的样本间关系。通过在排序后的演示对比解码过程中,引入相邻样本间的一致性机制,我们旨在改进用于机器人学习…...
Springboot使用AOP时,需不需要引入AspectJ?
Springboot使用AOP时,需不需要引入AspectJ? 在Spring Boot中使用AOP时,是否需要引入AspectJ取决于你选择的具体AOP实现方式。以下是详细分步说明: 1. 默认场景:使用Spring AOP(基于代理) 不需要引入AspectJ依赖&am…...
使用iis服务器模拟本地资源服务器unityaddressables热更新出错记录
editor中设置了using exculexing 模拟远程加载addressable可以实现资源热更新,build后的软件却没有成功。 iis服务器中mime中需要设置bundle的文件扩展名,时editor成功,build后失败 原因没有设置hash的扩展名,设置后editor和buil…...
17 一个高并发的系统架构如何设计
高并发系统的理解 第一:我们设计高并发系统的前提是该系统要高可用,起码整体上的高可用。 第二:高并发系统需要面对很大的流量冲击,包括瞬时的流量和黑客攻击等 第三:高并发系统常见的需要考虑的问题,如内存不足的问题,服务抖动的…...
MongoDb user自定义 role 添加 action(collStats, EstimateDocumentCount)
使用 mongosh cd mongsh_bin_path mongosh “mongodb://user:passip:port/db”这样就直接进入了对应的db 直接输入: 这样 role “read_only_role" 就获得了3个 action, 分别是 查询,列举集合,集合元数据查询 P.S: 如果没有 …...
我的AI工具箱Tauri版-Custom3DModelCreationforH2Panel卡通图片2D转绘3D
本教程基于自研的AI工具箱Tauri版进行ComfyUI工作流Custom3DModelCreationforH2Panel卡通图片2D转绘3D。 Custom3DModelCreationforH2Panel卡通图片2D转绘3D 基于先进的SD模型技术,能够将2D动漫图片高效转换为高清的3D图像,满足各种创作需求。通过智能算…...
1 HDFS
1 HDFS 1. HDFS概述2. HDFS架构3. HDFS的特性4. HDFS 的命令行使用5. hdfs的高级使用命令6. HDFS 的 block 块和副本机制6.1 抽象为block块的好处6.2 块缓存6.3 hdfs的文件权限验证6.4 hdfs的副本因子 7. HDFS 文件写入过程(非常重要)7.1 网络拓扑概念7.…...
14-6-3C++STL的list
(一)list的插入 1.list.insert(pos,elem);//在pos位置插入一个elem元素的拷贝,返回新数据的位置 #include <iostream> #include <list> using namespace std; int main() { list<int> lst; lst.push_back(10); l…...
GESP2023年12月认证C++六级( 第三部分编程题(2)工作沟通)
参考程序1代码: #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <string> #include <map> #include <iostream> #include <cmath> #include <vector> using name…...