Общее время, необходимое для прохождения пути, обозначенного данной строкой
Для заданного строкового пути, состоящего из символов «N», «S», «E» и «W», обозначающих движение на 1 единицу в направлениях на север, юг, восток и запад соответственно, задача состоит в том, чтобы найти время, необходимое для прохождения полного пути. путь, начинающийся из исходной точки, если путешествие по непосещенному и посещенному сегментам занимает 2 и 1 минуту соответственно.
Примеры :
Input: path = “NNES”
Output : 8Explanation: Since every segment is visited only once, cost = 2 * 4 = 8.
Input : path = “NSE”
Output : 5Explanation:
Step 1: Travel north. Time Taken = 2 minutes.
Step 2: Travel south on that same visited segment. Time Taken = 1 minutes.
Step 3: Travel east.Time Taken = 2 minutes. Therefore, total time taken = 2 + 1 + 2 = 5.
Подход: Идея состоит в том, чтобы использовать набор для хранения всех посещенных сегментов и перед посещением каждого сегмента проверять, присутствует ли он в наборе или нет. Выполните следующие действия, чтобы решить проблему.
- Инициализируйте набор s для хранения пары целых чисел. Набор будет хранить все посещенные сегменты.
- Инициализируйте два целых числа x = 0 и y = 0, обозначающие текущую позицию. Кроме того, инициализируйте переменную time = 0, чтобы сохранить общее время, необходимое для прохождения полного пути.
- Переместите строку и выполните следующие шаги.
- Инициализируйте два целых числа p и q равными x и y соответственно.
- Если path[i] равен 'N', приращение y , иначе, если path[i] равно 'S', уменьшает y, иначе если path[i] равно 'E', увеличивается x , иначе уменьшается x .
- Проверьте, существует ли сегмент { p + x , q + y } в наборе или нет. если он добавляет 1 к значению времени , в противном случае добавляет 2 к значению времени.
- Вставьте отрезок { p + x , q + y } в набор.
- После выполнения вышеуказанных шагов выведите значение времени.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(NlogN)
Вспомогательное пространство: O(N)