题目描述
假设 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 中的所有字符串都是 唯一 的。
解法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution:
def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
ans = []
mp = {v: i for i, v in enumerate(list2)}
mi = 2000
for i, v in enumerate(list1):
if v in mp:
t = i + mp[v]
if t < mi:
mi = t
ans = [v]
elif t == mi:
ans.append(v)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
Map<String, Integer> mp = new HashMap<>();
for (int i = 0; i < list2.length; ++i) {
mp.put(list2[i], i);
}
List<String> ans = new ArrayList<>();
int mi = 2000;
for (int i = 0; i < list1.length; ++i) {
if (mp.containsKey(list1[i])) {
int t = i + mp.get(list1[i]);
if (t < mi) {
ans = new ArrayList<>();
ans.add(list1[i]);
mi = t;
} else if (t == mi) {
ans.add(list1[i]);
}
}
}
return ans.toArray(new String[0]);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
unordered_map<string, int> mp;
for (int i = 0; i < list2.size(); ++i) mp[list2[i]] = i;
int mi = 2000;
vector<string> ans;
for (int i = 0; i < list1.size(); ++i) {
if (mp.count(list1[i])) {
int t = i + mp[list1[i]];
if (t < mi) {
ans.clear();
ans.push_back(list1[i]);
mi = t;
} else if (t == mi) {
ans.push_back(list1[i]);
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | func findRestaurant(list1 []string, list2 []string) []string {
mp := make(map[string]int)
for i, v := range list2 {
mp[v] = i
}
mi := 2000
var ans []string
for i, v := range list1 {
if _, ok := mp[v]; ok {
t := i + mp[v]
if t < mi {
ans = []string{v}
mi = t
} else if t == mi {
ans = append(ans, v)
}
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | function findRestaurant(list1: string[], list2: string[]): string[] {
let minI = Infinity;
const res = [];
const map = new Map<string, number>(list1.map((s, i) => [s, i]));
list2.forEach((s, i) => {
if (map.has(s)) {
const sumI = i + map.get(s);
if (sumI <= minI) {
if (sumI < minI) {
minI = sumI;
res.length = 0;
}
res.push(s);
}
}
});
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | use std::collections::HashMap;
use std::iter::FromIterator;
impl Solution {
pub fn find_restaurant(list1: Vec<String>, list2: Vec<String>) -> Vec<String> {
let map: HashMap<String, usize> = HashMap::from_iter(list1.into_iter().zip(0..));
let mut res = vec![];
let mut min_i = usize::MAX;
list2.into_iter().enumerate().for_each(|(i, key)| {
if map.contains_key(&key) {
let sum_i = map.get(&key).unwrap() + i;
if sum_i <= min_i {
if sum_i < min_i {
min_i = sum_i;
res.clear();
}
res.push(key);
}
}
});
res
}
}
|
方法二