599. 两个列表的最小索引总和

题目详情

假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。

你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。

示例 1:

1
2
3
输入: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
输出: ["Shogun"]
解释: 他们唯一共同喜爱的餐厅是“Shogun”。

示例 2:

1
2
3
输入: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 中的所有字符串都是 唯一 的

笔者解析

  1. 首先我们需要找到他们所共同喜欢的餐厅我们利用HashMap进行存储与匹配
  2. 我们找到最小索引和是多少，我们利用以前HashMap存储其下标值，进行帮助比较，利用队列存储符合餐厅与清除不符合餐厅
  3. 确定符合最小索引总和的餐厅数目（利用队列的长度求索）
  4. 返回将队列转化为数组返回

笔者代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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);
        }

        int index = Integer.MAX_VALUE;
        Queue<String> queue = new LinkedList<>();
        for (int i = 0; i < list2.length; i++) {
            if (map.containsKey(list2[i])){
                //使用钥匙找到值
                int b = map.get(list2[i]);
                if(b+i<index){
                 //如果搜索和小于，原来搜索和最小值，则清空列表重新计算
                    queue.clear();
                    queue.add(list2[i]);
                    index = b+i;
                }else if(b+i==index){
                  //若搜索和与最小值相等，则加入最小搜索值队列
                    queue.add(list2[i]);
                }
            }
        }
        return queue.toArray(new String[queue.size()]);
    }
}