599. Minimum Index Sum of Two Lists 「两个列表的最小索引总和」

假设小明和小红在考虑晚饭去哪吃,他们各自都有一个最喜欢饭馆的列表,列表内使用字符串保存饭馆名称。

你需要帮助他俩找出共同喜欢的饭馆,但是同时要求这个喜欢的饭馆的排号加和最小。如果有多个饭馆满足要求,那就不要求顺序地都输出。你可以认定在给出的列表中总能找到至少一个符合要求的饭馆。

例一:
输入: [“Shogun”, “Tapioca Express”, “Burger King”, “KFC”] [“Piatti”, “The Grill at Torrey Pines”, “Hungry Hunter Steakhouse”, “Shogun”]
输出: [“Shogun”]
解释: 只存在一个共同喜欢的饭馆“Shogun”。

例二:
输入: [“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. 单个列表中不存在重复元素。

本题思路主要是使用 HashMap 进行存储和查询。存储第一个表中的所有字符串,使用字符串作为键,使用下标作为值,这样在对第二个表查找相同字符串的时候就可以对两个下标进行计算和比较。

/*
 * 599. Minimum Index Sum of Two Lists
 * https://leetcode.com/problems/minimum-index-sum-of-two-lists/
 * https://www.whosneo.com/599-minimum-index-sum-of-two-lists/
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class FindRestaurant {
    public static void main(String[] args) {
        String[] list1 = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
        String[] list2 = {"Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"};

        FindRestaurant solution = new FindRestaurant();
        System.out.println("result = " + Arrays.toString(solution.findRestaurant(list1, list2)));
    }

    private String[] findRestaurant(String[] list1, String[] list2) {
        List<String> result = new ArrayList<>();

        HashMap<String, Integer> t = new HashMap<>();

        for (int i = 0; i < list1.length; i++)
            t.put(list1[i], i);

        int sum = Integer.MAX_VALUE;
        for (int i = 0; i < list2.length; i++) {
            if (t.containsKey(list2[i])) {
                int temp = i + t.get(list2[i]);
                if (temp < sum) {
                    result.clear();
                    result.add(list2[i]);
                    sum = temp;
                } else if (temp == sum) {
                    result.add(list2[i]);
                    sum = temp;
                }
            }
        }

        return result.toArray(new String[0]);
    }
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注