Сложность: easy
Дан массив paths, где paths[i] = [cityAi, cityBi] означает, что существует прямой путь из cityAi в cityBi. Вернуть конечный город, то есть город, из которого нет пути в другой город.
Гарантируется, что граф путей образует линию без циклов, поэтому будет ровно один конечный город.
Пример:
Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo"
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".
👨💻 Алгоритм:
1⃣Для каждого города cityBi в paths проверьте, является ли он кандидатом на конечный город.
2⃣Для каждого кандидата проверьте, нет ли пути, ведущего из него (cityAi == candidate).
3⃣Верните город, который не имеет исходящих путей.
😎 Решение:
class Solution {
function destCity($paths) {
foreach ($paths as $path) {
$candidate = $path[1];
$good = true;
foreach ($paths as $p) {
if ($p[0] === $candidate) {
$good = false;
break;
}
}
if ($good) {
return $candidate;
}
}
return "";
}
}Ставь 👍 и забирай 📚 Базу знаний