План курса / Все задачи / Алгоритмы и структуры данных
Оптимизация маршрута
средне
Дан массив строк path, содержащий один из символов:
U - движение вверх
D - движение вниз
L - движение влево
R - движение вправо
Нужно избавиться от всех циклов в маршруте и вернуть любой маршрут без петель. Обрати внимание, что нужно именно сократить маршрут, а не сделать новый. При этом маршрут не обязан быть кратчайшим.
Под петлей в задаче подразумеваются части маршрута, которые возвращают нас в точку в которой мы были несколько шагов назад и убрав которые место прибытия не изменится.
Ввод: path = ["D","R","U"]
Вывод: ["D","R","U"]
Пояснение: петель нет, маршрут остаётся без изменений (срезать нельзя)
Ограничения:
len(path) >= 1
public class Solution
{
public static List<string> OptimizePath(List<string> path)
{
var visited = new HashSet<(int, int)>();
var coords = new List<(int, int)> { (0, 0) };
visited.Add((0, 0));
var directions = new Dictionary<string, (int, int)>
{
["U"] = (0, 1), ["D"] = (0, -1), ["L"] = (-1, 0), ["R"] = (1, 0)
};
var result = new List<string>();
int x = 0, y = 0;
foreach (var direction in path)
{
var (dx, dy) = directions[direction];
x += dx;
y += dy;
if (visited.Contains((x, y)))
{
// Откатываемся по списку, очищая хешсет
while (coords[^1] != (x, y))
{
visited.Remove(coords[^1]);
coords.RemoveAt(coords.Count - 1);
result.RemoveAt(result.Count - 1);
}
}
else
{
visited.Add((x, y));
coords.Add((x, y));
result.Add(direction);
}
}
return result;
}
}
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <string>
using namespace std;
vector<string> optimizePath(vector<string> path) {
unordered_set<string> visited;
vector<pair<int, int>> coords;
coords.push_back(make_pair(0, 0));
visited.insert("0,0");
unordered_map<string, pair<int, int>> directions;
directions["U"] = make_pair(0, 1);
directions["D"] = make_pair(0, -1);
directions["L"] = make_pair(-1, 0);
directions["R"] = make_pair(1, 0);
vector<string> result;
int x = 0, y = 0;
for (size_t i = 0; i < path.size(); i++) {
string direction = path[i];
int dx = directions[direction].first;
int dy = directions[direction].second;
x += dx;
y += dy;
string key = to_string(x) + "," + to_string(y);
if (visited.count(key)) {
// откатываемся по списку, очищая хешсет
while (coords.back().first != x || coords.back().second != y) {
int cx = coords.back().first;
int cy = coords.back().second;
visited.erase(to_string(cx) + "," + to_string(cy));
coords.pop_back();
result.pop_back();
}
} else {
visited.insert(key);
coords.push_back(make_pair(x, y));
result.push_back(direction);
}
}
return result;
}
package main
func optimizePath(path []string) []string {
type point struct{ x, y int }
visited := make(map[point]bool)
coords := []point{{0, 0}}
visited[point{0, 0}] = true
directions := map[string]point{
"U": {0, 1}, "D": {0, -1}, "L": {-1, 0}, "R": {1, 0},
}
result := []string{}
x, y := 0, 0
for _, direction := range path {
d := directions[direction]
x += d.x
y += d.y
if visited[point{x, y}] {
// откатываемся по списку, очищая хешсет
for coords[len(coords)-1] != (point{x, y}) {
last := coords[len(coords)-1]
delete(visited, last)
coords = coords[:len(coords)-1]
result = result[:len(result)-1]
}
} else {
visited[point{x, y}] = true
coords = append(coords, point{x, y})
result = append(result, direction)
}
}
return result
}
import java.util.*;
public class Solution {
public List<String> optimizePath(List<String> path) {
Set<String> visited = new HashSet<>();
List<int[]> coords = new ArrayList<>();
coords.add(new int[]{0, 0});
visited.add("0,0");
Map<String, int[]> directions = Map.of(
"U", new int[]{0, 1}, "D", new int[]{0, -1},
"L", new int[]{-1, 0}, "R", new int[]{1, 0}
);
List<String> result = new ArrayList<>();
int x = 0, y = 0;
for (String direction : path) {
int[] d = directions.get(direction);
x += d[0];
y += d[1];
String key = x + "," + y;
if (visited.contains(key)) {
// откатываемся по списку, очищая хешсет
int[] last = coords.get(coords.size() - 1);
while (last[0] != x || last[1] != y) {
visited.remove(last[0] + "," + last[1]);
coords.remove(coords.size() - 1);
result.remove(result.size() - 1);
last = coords.get(coords.size() - 1);
}
} else {
visited.add(key);
coords.add(new int[]{x, y});
result.add(direction);
}
}
return result;
}
}
import java.util.*;
public class Solution {
public List<String> optimizePath(List<String> path) {
Set<String> visited = new HashSet<>();
List<int[]> coords = new ArrayList<>();
coords.add(new int[]{0, 0});
visited.add("0,0");
Map<String, int[]> directions = Map.of(
"U", new int[]{0, 1}, "D", new int[]{0, -1},
"L", new int[]{-1, 0}, "R", new int[]{1, 0}
);
List<String> result = new ArrayList<>();
int x = 0, y = 0;
for (String direction : path) {
int[] d = directions.get(direction);
x += d[0];
y += d[1];
String key = x + "," + y;
if (visited.contains(key)) {
// откатываемся по списку, очищая хешсет
int[] last = coords.get(coords.size() - 1);
while (last[0] != x || last[1] != y) {
visited.remove(last[0] + "," + last[1]);
coords.remove(coords.size() - 1);
result.remove(result.size() - 1);
last = coords.get(coords.size() - 1);
}
} else {
visited.add(key);
coords.add(new int[]{x, y});
result.add(direction);
}
}
return result;
}
}
from typing import *
def optimize_path(path: List[str]) -> List[str]:
visited = set()
coords = [(0, 0)]
visited.add((0, 0))
directions = {'U': (0, 1), 'D': (0, -1), 'L': (-1, 0), 'R': (1, 0)}
result = []
x, y = 0, 0
for direction in path:
dx, dy = directions[direction]
x, y = x + dx, y + dy
if (x, y) in visited:
# откатываемся по списку, очищая хешсет
while coords[-1] != (x, y):
visited.remove(coords.pop())
result.pop()
else:
visited.add((x, y))
coords.append((x, y))
result.append(direction)
return result
Оценка сложности
Время: O(n), где n — длина маршрута
Память: O(n) для хранения посещённых точек и координат
Идея: храним все посещённые точки в set и их порядок в coords. Если пришли в уже посещённую точку — это петля. Откатываемся назад по coords, удаляя точки из set и направления из result, пока не дойдём до этой точки.