LeetCode 599: 两个列表的最小索引总和 Minimum Index Sum of Two Lists
题目:
假设 Andy 和 Doris 想在晚餐时选择一家餐厅,并且他们都有一个表示最喜爱餐厅的列表,每个餐厅的名字用字符串表示。
Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.
你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。如果答案不止一个,则输出所有答案并且不考虑顺序。你可以假设总是存在一个答案。
You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.
示例 1:
输入: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"] 输出: ["Shogun"] 解释: 他们唯一共同喜爱的餐厅是“Shogun”。
示例 2:
输入: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["KFC", "Shogun", "Burger King"] 输出: ["Shogun"] 解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”,它有最小的索引和1(0+1)。
提示:
- 两个列表的长度范围都在 [1, 1000] 内。
- 两个列表中的字符串的长度将在 [1,30] 的范围内。
- 下标从 0 开始,到列表的长度减 1。
- 两个列表都没有重复的元素。
Note:
- The length of both lists will be in the range of [1, 1000].
- The length of strings in both lists will be in the range of [1, 30].
- The index is starting from 0 to the list length minus 1.
- No duplicates in both lists.
解题思路:
两个字符串数组,找重复出现的元素,返回其索引和最小的目标数组。最容易想到的解法就是用哈希映射解题,Key 存储其数组的每个元素值,Value 存储其下标索引。第一次遍历将其中一个数组添加到哈希映射,第二次遍历查找目标元素。需要维护一个最小索引和来保证查询的目标索引和为最小。
哈希表解题:
Java:
class Solution { public String[] findRestaurant(String[] list1, String[] list2) { Map<String, Integer> map = new HashMap<>();//建立哈希映射 for (int i = 0; i < list1.length; i++)//初次遍历将一个数组建立映射关系 map.put(list1[i], i); List<String> res = new ArrayList<>();//待返回的目标数组 int sum = Integer.MAX_VALUE;//sum为当前满足条件的最小索引和 for (int i = 0; i < list2.length; i++) {//第二次遍历查找目标元素 if (map.containsKey(list2[i])) { int tmp = i + map.get(list2[i]);//当前索引和 if (tmp < sum) {//如果当前索引和更小 res.clear();//清除目标数组 res.add(list2[i]);//添加该元素 sum = tmp;// 刷新最小索引和 } else if (tmp == sum)//如果索引和相等 res.add(list2[i]);//只添加元素 } } return res.toArray(new String[res.size()]);//转成 string 数组 } }
Python:
class Solution: def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]: hash_map = dict()# 建立哈希映射 for i, s in enumerate(list1):# 初次遍历将一个数组建立映射关系 hash_map[s] = i min_sum = 2001# 当前满足条件的最小索引和 res = list()# 待返回的目标数组 for i, s in enumerate(list2):# 第二次枚举遍历查找目标元素 if s in hash_map: tmp = i+hash_map[s]# 当前索引和 if tmp < min_sum:# 如果当前索引和更小 res.clear()# 清除目标数组 res.append(s)# 添加该元素 min_sum = tmp# 刷新最小索引和 elif tmp == min_sum:# 如果索引和相等 res.append(s)# 只添加元素 return res
操作索引解题:
这种解法非常巧妙,虽然效率很低。以下解释摘自 LeetCode,可以作为参考扩展思路:
另一种可以遍历不同 sumsum (下标和),并判断是否有字符串分别出现在 list1 和 list2 中且下标和为 sum。
现在我们知道下标和的值 sum 数值范围从 0 到 m + n - 1。这里 m 和 n 分别是 list1 和 list2 的长度,我们现在可以升序枚举 sum ,对于每个 sum,我们遍历 list1,假设当前下标为 i,为了得到下标和 sum,list2 中的下标 j 为 sum−i。通过这样的办法,我们不需要遍历 list2,而可以直接通过计算得到在 list2 中对应的下标。
对于每个 sum,我们遍历 list1 的所有下标,一旦有 list1 和 list2 中的字符串匹配,就把匹配字符串放入一个 res 列表中。
我们对 sum 升序数组中所有值做相同的过程,对于每个 sum 遍历完一遍 list1 之后,我们检查 res 列表是否为空。如果是空的,我们继续遍历下一个 sum 数组。如果不为空,当前的 res 就是最小下标和的数组。这是因为我们遍历 sum 的顺序是升序的,所以第一个找到的列表就是结果列表。
Java:
class Solution { public String[] findRestaurant(String[] list1, String[] list2) { List<String> res = new ArrayList<>(); for (int sum = 0; sum < list1.length + list2.length - 1; sum++) { for (int i = 0; i <= sum; i++) { if (i < list1.length && sum - i < list2.length && list1[i].equals(list2[sum - i])) res.add(list1[i]); } if (res.size() > 0) break;//一旦找到最小索引和序列直接结束遍历,因为sum是递增的,之后得到的索引和一定更大 } return res.toArray(new String[res.size()]); } }
Python
class Solution: def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]: res = list() list1_size, list2_size = len(list1), len(list2) for min_sum in range(list1_size+list2_size-1): for i in range(min_sum+1): if i < list1_size and min_sum-i < list2_size and list1[i] == list2[min_sum-i]: res.append(list1[i]) if len(res) > 0:# 一旦找到最小索引和序列直接结束遍历,因为sum是递增的,之后得到的索引和一定更大 break return res
欢迎关注微。信公。众号:爱写Bug
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
走进JavaWeb技术世界16:极简配置的SpringBoot
本系列文章将整理到我在GitHub上的《Java面试指南》仓库,更多精彩内容请到我的仓库里查看 https://github.com/h2pl/Java-Tutorial 喜欢的话麻烦点下Star哈 文章首发于我的个人博客: www.how2playlife.com 本文是微信公众号【Java技术江湖】的《走进JavaWeb技术世界》其中一篇,本文部分内容来源于网络,为了把本文主题讲得清晰透彻,也整合了很多我认为不错的技术博客内容,引用其中了一些比较好的博客文章,如有侵权,请联系作者。 该系列博文会告诉你如何从入门到进阶,从servlet到框架,从ssm再到SpringBoot,一步步地学习JavaWeb基础知识,并上手进行实战,接着了解JavaWeb项目中经常要使用的技术和组件,包括日志组件、Maven、Junit,等等内容,以便让你更完整地了解整个JavaWeb技术体系,形成自己的知识框架。为了更好地总结和检验你的学习成果,本系列文章也会提供每个知识点对应的面试题以及参考答案。 如果对本系列文章有什么建议,或者是有什么疑问的话,也可以关注公众号【Java技术江湖】联系作者,欢迎你参...
- 下一篇
VLOOK V9.2 发布:Markdown 编辑器 Typora 的增强插件
VLOOK™ 是针对由Typora(目前最好的跨平台 Markdown 编辑器,没有之一)导出的 HTML 文件进行增强的插件。VLOOK™ 为开源软件,遵从 MIT 许可证。 VLOOK 插件主要包括: 排版增强:针对 Typora 编辑模式,以及导出的 HTML 文件增加更实用、美观的文档排版与样式; 功能增强:针对导出的 HTML 文件提供文档导航、评审演示、插图浏览、内容交互、信息缺失检测等功能。 有关 VLOOK 特性的详细介绍、样例及使用说明详见《VLOOK 快速参考手册》 有关脚本化图表的详细介绍、样例及使用说明详见《脚本化图表 for Markdown》 主题样式 针对 VLOOK 内置多套优化的主题样式(在导出 HTML 通过 Typora 的「主题」菜单选择名称以 VLOOK 打头的主题); Hope 海洋之心:预览 > Joint 榫卯:预览 > Geek 极邃:预览 > Fancy 慕幻:预览 > 所有主题的文档导出为 HTML 后,都支持Light (明亮)与Dark (黑暗)模式。 目前发布了 9.2 版本,此版本更新内容: 新增 重构了 Dark Mode...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- SpringBoot2整合Thymeleaf,官方推荐html解决方案
- CentOS关闭SELinux安全模块
- CentOS7设置SWAP分区,小内存服务器的救世主
- Docker安装Oracle12C,快速搭建Oracle学习环境
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库