Задача: 1496. Path Crossing
Дана строка 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:
def isPathCrossing(self, path: str) -> bool:
moves = {'N': (0, 1), 'S': (0, -1), 'E': (1, 0), 'W': (-1, 0)}
visited = {(0, 0)}
x = y = 0
for c in path:
dx, dy = moves[c]
x += dx
y += dy
if (x, y) in visited:
return True
visited.add((x, y))
return False
👉Новости 👉Платформа