Сложность: medium
На кампусе, представленном в виде двумерной сетки, есть n рабочих и m велосипедов, где n <= m. Каждый рабочий и велосипед имеют координаты на этой сетке.
Мы назначаем каждому рабочему уникальный велосипед таким образом, чтобы сумма Манхэттенских расстояний между каждым рабочим и назначенным ему велосипедом была минимальной.
Верните минимально возможную сумму Манхэттенских расстояний между каждым рабочим и назначенным ему велосипедом.
Манхэттенское расстояние между двумя точками p1 и p2 вычисляется как Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
Пример:
Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]
👨💻 Алгоритм:
1⃣Для каждого рабочего, начиная с рабочего с индексом 0, пройдите по всем велосипедам и назначьте велосипед рабочему, если он доступен (visited[bikeIndex] = false). После назначения велосипеда отметьте его как недоступный (visited[bikeIndex] = true). Добавьте Манхэттенское расстояние от этого назначения к общей текущей сумме расстояний, представленной currDistanceSum, и выполните рекурсивный вызов для следующего рабочего.
2⃣Когда рекурсивный вызов завершится, сделайте велосипед снова доступным, установив visited[bikeIndex] в false. Если мы назначили велосипеды всем рабочим, сравните currDistanceSum с smallestDistanceSum и обновите smallestDistanceSum соответственно.
3⃣Перед назначением любого велосипеда рабочему, проверьте, если currDistanceSum уже больше или равен smallestDistanceSum. Если это так, пропустите остальных рабочих и вернитесь. Это связано с тем, что currDistanceSum может только увеличиваться, и таким образом мы не найдем лучший результат, чем smallestDistanceSum, используя текущую комбинацию рабочих и велосипедов.
😎 Решение:
class Solution {
function indexPairs($text, $words) {
$wordsSet = array_flip($words);
$ans = [];
for ($i = 0; $i < strlen($text); $i++) {
for ($j = $i; $j < strlen($text); $j++) {
if (isset($wordsSet[substr($text, $i, $j - $i + 1)])) {
$ans[] = [$i, $j];
}
}
}
return $ans;
}
}Ставь 👍 и забирай 📚 Базу знаний