每日一题---数组中两个字符串的最小距离

devtools/2025/3/16 17:20:34/

数组中两个字符串的最小距离

给定一个字符串数组strs,再给定两个字符串str1和str2,返回在strs中str1和str2的最小距离,如果str1或str2为null,或不在strs中,返回-1。

链接:数组中两个字符串的最小距离__牛客网
来源:牛客网
 

输入描述:

输入包含有多行,第一输入一个整数n(1≤n≤105)(1 \leq n \leq 10^5)(1≤n≤105),代表数组strs的长度,第二行有两个字符串分别代表str1和str2,接下来n行,每行一个字符串,代表数组strs (保证题目中出现的所有字符串长度均小于等于10)。

输出描述:

输出一行,包含一个整数,代表返回的值。

示例1:

输入

1
CD AB
CD

输出

-1

示例2:

输入

5
QWER 666
QWER
1234
qwe
666
QWER

输出

1
备注:

时间复杂度O(n)O(n),额外空间复杂度O(1)O(1)

解题:

解法一:暴力解法

可以定义两层for循环,i  j  ,当i找到一个str1时,就让j向后找最近的str2,并更新最近的距离ret,

然后让i遍历所有的字符串,得到最近距离。但这样显然超时了,不过我们可以对这个方法进行优化。

解法二:模拟

优化的方法有很多,比如可以先循环一遍找到所有的str1,str2并把下标记录下来,然后对这两个下标数组找最小距离,但这样空间复杂度就高了。

不妨在读取字符串的时候尝试用两个单独的数字prev1,prev2记录str1与str2的下标,并随着读取不断更新当前的下标。即:prev1代表当前最靠右的str1,prev2代表当前最靠右的str2,然后每次ret就更新prev1-prev2或prev1-prev2,表示向左寻找距离最近的另一个字符串,由于读取是向右读取的,这样就可以遍历到全部的情况

代码如下:

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();in.nextLine();String str1 = in.next();String str2 = in.next();int prev1 = -1;//str1的最靠右的下标int prev2 = -1;//str2的最靠右的下标//注意要找距离最近的,所以初始化成最大的int ret = 0x3f3f3f3f;for(int i = 0; i < n; i++) {String tmp = in.nextLine();//不用创建数组,直接在读取时更新即可if(tmp.equals(str1)) {prev1 = i;//更新str1的下标if(prev2 != -1)ret = Math.min(prev1 - prev2, ret);}if(tmp.equals(str2)) {prev2 = i;//更新str2的下标if(prev1 != -1)ret = Math.min(prev2 - prev1, ret);}}System.out.println(ret == 0x3f3f3f3f ? -1 : ret);//如果没更新ret说明没找到}
}


http://www.ppmy.cn/devtools/167610.html

相关文章

MySQL 8 主从同步安装与配置

拟机&#xff0c;由 CentOS 换成了 Ubuntu&#xff0c;用 Xteminal 连接之后&#xff0c;为了方便改配置文件&#xff0c;把文件权限改成 666 了&#xff0c;结果因为这个调半天&#xff0c;一直以为是网络问题或者是配置问题。要注意为了防止配置文件被未经授权的用户修改&…

STM32 单片机常见的 8 种输入输出模式

STM32 单片机常见的 8 种输入输出模式 文章目录 STM32 单片机常见的 8 种输入输出模式1. 浮空输入模式 (GPIO_Mode_IN_FLOATING)介绍使用场景示例代码 2. 上拉输入模式 (GPIO_Mode_IPU)介绍使用场景示例代码 3. 下拉输入模式 (GPIO_Mode_IPD)介绍使用场景示例代码 4. 模拟输入模…

拥有一台云服务器能做什么呢?

拥有一台云服务器就像拥有了一台24小时在线的远程电脑&#xff0c;你可以通过互联网随时随地管理它。它的用途非常广泛&#xff0c;无论是个人学习、开发测试&#xff0c;还是企业级应用部署&#xff0c;都能发挥重要作用。以下是常见的应用场景&#xff0c;按需求分类整理&…

SwanLab私有化部署教程!

SwanLab私有化部署版面向所有个人用户免费开放&#xff0c;部署方案基于Docker Compose&#xff0c;能非常轻松地部署在 Windows/MacOS/Linux 机器上&#xff0c;希望能成为各位训练师的独门炼丹利器。 下面我们会介绍一下如何安装私有化部署版。 1. SwanLab介绍 SwanLab 是…

Unity 封装一个依赖于MonoBehaviour的计时器(上) 基本功能

灵感来自下面这本书的协程部分,因此我就自己尝试写了一个 我的新书Unity3D游戏开发&#xff08;第3版&#xff09; | 雨松MOMO程序研究院 如果你不知道什么是协程:unity保姆级教程之协同程序_unity协同-CSDN博客 一句话概括:协程就是单线程的异步操作,其作用于Unity的主线程 1…

如何在github上参与开源项目

1. 创建 GitHub 账号 如果你还没有 GitHub 账号&#xff0c;首先需要注册一个&#xff1a; 访问 GitHub 官网。 点击右上角的“Sign up”按钮&#xff0c;填写注册信息并完成注册。 2. 找到感兴趣的项目 GitHub 上有成千上万的开源项目&#xff0c;你可以通过以下方式找到感兴趣…

prototype和proto的区别

在 JavaScript 中&#xff0c;prototype 和 __proto__ 都与原型链和继承机制有关&#xff0c;但它们的含义和作用是不同的。下面来详细讲解它们的区别。 一、prototype 和 proto 的区别 特性prototype__proto__作用构造函数的原型对象实例对象的隐式原型类型对象对象访问方式构…

数据库管理-第302期 国产类RAC架构数据库网络连接方式(20250314)

数据库管理302期 2025-03-14 数据库管理-第302期 国产类RAC架构数据库网络连接方式&#xff08;20250314&#xff09;1 Oracle RAC2 DMDSC3 YAC4 KES RAC总结 数据库管理-第302期 国产类RAC架构数据库网络连接方式&#xff08;20250314&#xff09; 作者&#xff1a;胖头鱼的鱼…