LeetCode Minimum Index Sum of Two Lists
2024-10-08 10:46:02
原题链接在这里:https://leetcode.com/problems/minimum-index-sum-of-two-lists/description/
题目:
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.
Example 1:
Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".
Example 2:
Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
Output: ["Shogun"]
Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (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.
题解:
把list1的element 和对应的index放进HashMap<String, Integer> hm中. 再iterate list2, 如果list2的element在hm中比较index相加是否比minIndexSum小,若比minIndexSum小,清空res重新加, 更新minIndexSum. 若相等直接加进res中.
Time Complexity: O(list1.length + list2.length)
Space: O(list1.length).
AC Java:
class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
List<String> res = new ArrayList<String>();
int minIndexSum = Integer.MAX_VALUE;
HashMap<String, Integer> hm = new HashMap<String, Integer>();
for(int i = 0; i<list1.length; i++){
hm.put(list1[i], i);
} for(int j = 0; j<list2.length; j++){
if(hm.containsKey(list2[j])){
int i = hm.get(list2[j]);
if(i+j < minIndexSum){
res.clear();
res.add(list2[j]);
minIndexSum = i+j;
}else if(i+j == minIndexSum){
res.add(list2[j]);
}
}
} return res.toArray(new String[res.size()]);
}
}
最新文章
- TransMac Win系统下制作 OS X启动盘图文教程超详细小白版
- python运算符
- CentOS 7 配置静态 ip
- 8款适合乐队、歌手和音乐家免费 WordPress 主题
- 使用/调用 函数的时候, 前面加不加 对象或 this?
- 用OPencv配置vs2010
- Java 垃圾收集与内存回收
- 为什么匿名内部类参数必须为final类型(转载)
- 【专访】【Spring常见问题汇总】【05】
- Android之LinkedHashMap实现LRU
- 一个用 js 实现点阵图的编辑器演示
- EOJ 3242 重复数
- this的四种用法
- Java 多线程之悲观锁与乐观锁
- 两个select一个选中,另一个就没有选中的那个值
- vue+element-ui中的表单验证(电话等等)
- Lab 3-4
- maven聚合工程tomcat插件启动没有 Starting ProtocolHandler [";http-bio-8081";]
- flexible.js移动端适配安卓高分辨不兼容问题
- [UE4]C 语言动态数组
热门文章
- 安装MySQL的详细步骤
- css系列(5)css的运用(一)
- linux 定时任务未执行php脚本
- python + Streaming框架的MR实践与优化
- 主攻ASP.NET MVC4.0之重生:Jquery Mobile 表单元素
- RewriteRule ^(.*)$ index.php/$1 [QSA,PT,L] 是什么意思?
- PHP面试题汇总一
- nginx日志中$request_body 十六进制字符(\\x22) 引号问题处理记录
- Java Hibernate 5.3.x
- 关于v4l2的一点变更