前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 599: 两个列表的最小索引总和 Minimum Index Sum of Two Lists

LeetCode 599: 两个列表的最小索引总和 Minimum Index Sum of Two Lists

作者头像
爱写bug
发布2019-10-22 23:23:49
1.1K0
发布2019-10-22 23:23:49
举报
文章被收录于专栏:爱写Bug

题目:

假设 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:

代码语言:javascript
复制
输入:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
输出: ["Shogun"]
解释: 他们唯一共同喜爱的餐厅是“Shogun”。

示例 2:

代码语言:javascript
复制
输入:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
输出: ["Shogun"]
解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”,它有最小的索引和1(0+1)。

提示:

  1. 两个列表的长度范围都在 [1, 1000] 内。
  2. 两个列表中的字符串的长度将在 [1,30] 的范围内。
  3. 下标从 0 开始,到列表的长度减 1。
  4. 两个列表都没有重复的元素。

Note:

  1. The length of both lists will be in the range of [1, 1000].
  2. The length of strings in both lists will be in the range of [1, 30].
  3. The index is starting from 0 to the list length minus 1.
  4. No duplicates in both lists.

解题思路:

两个字符串数组,找重复出现的元素,返回其索引和最小的目标数组。最容易想到的解法就是用哈希映射解题,Key 存储其数组的每个元素值,Value 存储其下标索引。第一次遍历将其中一个数组添加到哈希映射,第二次遍历查找目标元素。需要维护一个最小索引和来保证查询的目标索引和为最小。

哈希表解题:

Java:

代码语言:javascript
复制
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:

代码语言:javascript
复制
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 的顺序是升序的,所以第一个找到的列表就是结果列表。

<!--作者:LeetCode-->!--链接:https://leetcode-cn.com/problems/minimum-index-sum-of-two-lists/solution/liang-ge-lie-biao-de-zui-xiao-suo-yin-zong-he-by-l/--<!--来源:力扣(LeetCode)-->

Java:

代码语言:javascript
复制
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

代码语言:javascript
复制
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
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-10-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 爱写Bug 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目:
  • 解题思路:
  • 哈希表解题:
  • 操作索引解题:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档