Сложность: easy
Дана строка path, где path[i] = 'N', 'S', 'E' или 'W', каждая из которых представляет движение на одну единицу на север, юг, восток или запад соответственно. Вы начинаете с точки (0, 0) на 2D плоскости и идете по пути, указанному в path.
Верните true, если путь пересекает сам себя в какой-либо точке, то есть если вы в какой-то момент окажетесь в месте, которое уже посещали ранее. В противном случае верните false.
Пример:
Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.
👨💻 Алгоритм:
1⃣Инициализация переменных:
Создать хэш-карту moves, которая сопоставляет символы 'N', 'S', 'E', 'W' с соответствующими значениями.
Инициализировать множество visited с начальной точкой (0, 0).
Установить начальные координаты x = 0 и y = 0.
2⃣Проход по строке path:
Для каждого символа c в path получить значения (dx, dy) из moves[c].
Обновить координаты: добавить dx к x и dy к y.
Проверить, содержится ли текущая точка (x, y) в visited. Если да, вернуть true.
Добавить текущую точку (x, y) в visited.
3⃣Возврат результата:
Если ни одна точка не пересекалась, вернуть false.
😎 Решение:
class Solution {
function isPathCrossing($path) {
$moves = [
'N' => [0, 1], 'S' => [0, -1],
'E' => [1, 0], 'W' => [-1, 0]
];
$visited = [[0, 0]];
$x = 0;
$y = 0;
foreach (str_split($path) as $c) {
list($dx, $dy) = $moves[$c];
$x += $dx;
$y += $dy;
$point = [$x, $y];
if (in_array($point, $visited)) {
return true;
}
$visited[] = $point;
}
return false;
}
}Ставь 👍 и забирай 📚 Базу знаний