1. 代码段小站首页
  2. 算法

leetcode599-两个列表的最小索引总和

彭晨涛 • • 算法 • 阅读 9

原题

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

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

示例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. 两个列表的长度范围都在 [1, 1000]内。
  2. 两个列表中的字符串的长度将在[1，30]的范围内。
  3. 下标从0开始，到列表的长度减1。
  4. 两个列表都没有重复的元素。

解法

思想

哈希表，将第一个列表中的字符串和下标对应起来，然后遍历第二个列表找最小下标之和。

代码

class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        Map<String,Integer> map = new HashMap<>();
        int newLength = 0;
        int minSum = 2000;
        for(int i = 0;i<list1.length;i++){
            map.put(list1[i],i);
        }
        for(int i = 0;i<list2.length;i++){
            if(map.containsKey(list2[i])){
                int n = i + map.get(list2[i]);
                if(n<minSum){
                    list1[0] = list2[i];
                    newLength = 1;
                    minSum = n;
                }else if(n == minSum){
                    list1[newLength] = list2[i];
                    newLength++;
                }
            }
        }

        String[] ret = new String[newLength];
        System.arraycopy(list1,0,ret,0,newLength);
        return ret;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode599-%e4%b8%a4%e4%b8%aa%e5%88%97%e8%a1%a8%e7%9a%84%e6%9c%80%e5%b0%8f%e7%b4%a2%e5%bc%95%e6%80%bb%e5%92%8c/

赞 (0)
彭晨涛彭晨涛管理者
0 0
上一篇 2019年12月21日 22:54
下一篇 2019年12月22日 22:32

相关推荐

  • leetcode561-数组拆分I

    原题 给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从1 到 n 的 min(ai, b...

    彭晨涛 彭晨涛
    算法 2019年11月18日
    060

  • leetcode217-存在重复元素

    原题 给定一个整数数组，判断是否存在重复元素。 如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。 示例1： 输入： [1,2,3...

    彭晨涛 彭晨涛
    算法 2019年12月18日
    040

  • leetcode73-矩阵置零

    原题 给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。 示例 1: 输入: [   [1,1,1],  ...

    彭晨涛 彭晨涛
    算法 2020年5月14日
    080

  • leetcode80-删除排序数组中的重复项II

    原题 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外...

    彭晨涛 彭晨涛
    算法 2020年5月26日
    0110

  • leetcode121-买卖股票的最佳时机

    原题 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。 注意你不能在...

    彭晨涛 彭晨涛
    算法 2020年3月9日
    080

  • leetcode110-平衡二叉树

    原题 给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1:  给定二叉树 [...

    彭晨涛 彭晨涛
    算法 2020年1月17日
    0160
  • leetcode611-有效三角形的个数 算法

    leetcode611-有效三角形的个数

    原题 给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。 示例1: 输入： [2,2,3,4] 输出： 3 解释： 有效的组合是: 2,3,4 (使用...

    彭晨涛 彭晨涛
    2020年2月8日
    050

  • leetcode4-寻找两个有序数组的中位数

    这道题我没想出符合条件的思路 原题 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m...

    彭晨涛 彭晨涛
    算法 2020年1月9日
    0250
  • leetcode540-有序数组中的单一元素 算法

    leetcode540-有序数组中的单一元素

    原题 给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。 示例1: 输入： [1,1,2,3,3,4,4,8,8] 输出： 2 示例2: 输入...

    彭晨涛 彭晨涛
    2020年2月25日
    0630

  • 程序员面试金典01.07-旋转矩阵

    原题（来源Leetcode） 给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。 不占用额外内存空间能否做到？ 示例 ...

    彭晨涛 彭晨涛
    算法 2020年4月7日
    0320

发表回复

登录后才能评论