class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
}
};
599. 两个列表的最小索引总和
假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。
示例 1:
输入: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"] 输出: ["Shogun"] 解释: 他们唯一共同喜爱的餐厅是“Shogun”。
示例 2:
输入:list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["KFC", "Shogun", "Burger King"] 输出: ["Shogun"] 解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。
提示:
1 <= list1.length, list2.length <= 10001 <= list1[i].length, list2[i].length <= 30 list1[i] 和 list2[i] 由空格 ' ' 和英文字母组成。list1 的所有字符串都是 唯一 的。list2 中的所有字符串都是 唯一 的。相似题目
原站题解
golang 解法, 执行用时: 48 ms, 内存消耗: 7 MB, 提交时间: 2021-06-18 10:02:13
func findRestaurant(list1 []string, list2 []string) (ans []string) {
n1, n2 := len(list1), len(list2)
for sum := 0; sum < n1 + n2 - 1; sum++ {
if len(ans) > 0 {
break
}
for i := 0; i <= sum; i++ {
if i < n1 && sum-i < n2 && list1[i] == list2[sum-i] {
ans = append(ans, list1[i])
}
}
}
return ans
}
golang 解法, 执行用时: 48 ms, 内存消耗: 7.1 MB, 提交时间: 2021-06-17 16:53:26
func findRestaurant(list1 []string, list2 []string) []string {
m := math.MaxInt16
mp := map[int][]string{}
var k int
for i, a := range list1 {
for j, b := range list2 {
if a == b {
k = i+j
mp[k] = append(mp[k], a)
if k < m {
m = k
}
break
}
}
}
return mp[m]
}