Member 13503909 Ответов: 3

Вопрос кодирование зарегистрироваться ! !

Алиса должна идти на работу из своего дома. Он как-то находит его в первый же день и записывает . В офисе она находит путь длиннее и укорачивает его.

Учитывая длинную цепочку пути, сократите ее. Результат должен быть отсортирован лексикографически .

Пример : SSNE будет упрощен как ES

S означает Юг, N-Север, W-Запад , E - Восток.

Что я уже пробовал:

Я думаю удалить все те же символы, которые встречаются вместе, и сохранить только один из них.

напр.:
SSSNNEW -> SNEW -> ENSW(ответ)

а позже отсортируйте строку лексически. Это правильный путь ??

3 Ответов

Рейтинг:
26

OriginalGriff

Нет. Посмотрите на пример:

SSNE -> ES
Что вам нужно сделать, так это удалить противоположности: Север и Юг, Восток и Запад. Когда вы удалили пары, вы можете сортировать.

CPallini

5.

Рейтинг:
2

Patrice T

Цитата:
Я думаю удалить все те же символы, которые встречаются вместе, и сохранить только один из них.

Неправильный
принцип заключается в том, что Н и С противоположных направлениях, одинаковы для Е и В.
Это означает, что если у вас есть и то, и другое; ход С будет отменить ход Н, то же самое с Е и В.
Так что СССТНовый -> SСТФу -> SФУ -> S

Рейтинг:
2

Member 14901879

мы можем решить эту проблему с помощью стека если стек пуст нажмите на стек

всегда сравнивайте верхнюю часть стека с текущим элементом в строке.

если вершина-это S, а элемент-S, то нажмите S. аналогично для N, E и W.

если top-это S, а element-N или наоборот, то выскакивайте из стека и не толкайте.
если вершина-W, а элемент-E или наоборот, то выскакивайте из стека и не толкайте.

затем извлеките все элементы, оставшиеся в стеке, и сохраните их в строке, а затем отсортируйте строку и распечатайте ее.

CPallini

Вы немного опоздали на вечеринку, не так ли?