Задача: 599. Minimum Index Sum of Two Lists
Сложность: easy
Даны два массива строк list1 и list2, необходимо найти общие строки с наименьшей суммой индексов.
Общая строка - это строка, которая появляется и в list1, и в list2.
Общая строка с наименьшей суммой индексов - это общая строка, такая, что если она появилась в list1[i] и list2[j], то i + j должно быть минимальным значением среди всех других общих строк.
Верните все общие строки с наименьшей суммой индексов. Верните ответ в любом порядке.
Пример:
Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".
👨💻 Алгоритм:
1⃣Для каждой строки из list1, сравниваем её с каждой строкой из list2, обходя весь список list2. Используем хэш-таблицу map, которая содержит элементы в виде (сумма: список строк). Здесь сумма относится к сумме индексов совпадающих элементов, а список строк соответствует списку совпадающих строк, чья сумма индексов равна этой сумме.
2⃣Во время сравнений, когда находится совпадение строки на i-м индексе из list1 и j-м индексе из list2, создаём запись в map, соответствующую сумме i + j, если такая запись ещё не существует. Если запись с этой суммой уже существует, добавляем текущую строку в список строк, соответствующих сумме i + j.
3⃣В конце обходим ключи в map и находим список строк, соответствующих ключу с минимальной суммой.
😎 Решение:
import java.util.*;
public class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
HashMap map = new HashMap();
for (int i = 0; i < list1.length; i++) {
for (int j = 0; j < list2.length; j++) {
if (list1[i].equals(list2[j])) {
if (!map.containsKey(i + j)) {
map.put(i + j, new ArrayList());
}
map.get(i + j).add(list1[i]);
}
}
}
int minIndexSum = Integer.MAX_VALUE;
for (int key : map.keySet()) {
minIndexSum = Math.min(minIndexSum, key);
}
return map.get(minIndexSum).toArray(new String[0]);
}
}
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Даны два массива строк list1 и list2, необходимо найти общие строки с наименьшей суммой индексов.
Общая строка - это строка, которая появляется и в list1, и в list2.
Общая строка с наименьшей суммой индексов - это общая строка, такая, что если она появилась в list1[i] и list2[j], то i + j должно быть минимальным значением среди всех других общих строк.
Верните все общие строки с наименьшей суммой индексов. Верните ответ в любом порядке.
Пример:
Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".
👨💻 Алгоритм:
1⃣Для каждой строки из list1, сравниваем её с каждой строкой из list2, обходя весь список list2. Используем хэш-таблицу map, которая содержит элементы в виде (сумма: список строк). Здесь сумма относится к сумме индексов совпадающих элементов, а список строк соответствует списку совпадающих строк, чья сумма индексов равна этой сумме.
2⃣Во время сравнений, когда находится совпадение строки на i-м индексе из list1 и j-м индексе из list2, создаём запись в map, соответствующую сумме i + j, если такая запись ещё не существует. Если запись с этой суммой уже существует, добавляем текущую строку в список строк, соответствующих сумме i + j.
3⃣В конце обходим ключи в map и находим список строк, соответствующих ключу с минимальной суммой.
😎 Решение:
import java.util.*;
public class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
HashMap map = new HashMap();
for (int i = 0; i < list1.length; i++) {
for (int j = 0; j < list2.length; j++) {
if (list1[i].equals(list2[j])) {
if (!map.containsKey(i + j)) {
map.put(i + j, new ArrayList());
}
map.get(i + j).add(list1[i]);
}
}
}
int minIndexSum = Integer.MAX_VALUE;
for (int key : map.keySet()) {
minIndexSum = Math.min(minIndexSum, key);
}
return map.get(minIndexSum).toArray(new String[0]);
}
}
Ставь 👍 и забирай 📚 Базу знаний