Минимальное время, необходимое для печати заданной строки из круглого контейнера на основе заданных условий

Опубликовано: 21 Сентября, 2022

Для данного кругового контейнера, состоящего из строчных букв от «a» до «z», указателя , первоначально указывающего на алфавит «a», и строки str задача состоит в том, чтобы найти минимальное время, необходимое для печати данной строки str из кругового контейнер, основанный на следующих операциях, которые можно выполнять над каждым символом:

  • Переместите указатель на один символ против часовой стрелки или по часовой стрелке за единицу времени.
  • Напечатайте символ за одну единицу времени, а затем переместите указатель на следующий индекс строки.

Пример:

Input: str = “zcd”
Output: 8
Explanation: The steps are as follows:

  • Move the pointer anti-clockwise to ‘z’ in 1 second
  • Type the character ‘z’ in 1 second
  • Move the pointer clockwise to ‘c’ in 3 seconds
  • Type the character ‘c’ in 1 second
  • Move the pointer clockwise to ‘d’ in 1 seconds
  • Type the character ‘d’ in 1 second.

Input: str =”zjpc”
Output: 34
Explanation: The steps are as follows:

  • Move the pointer anti-clockwise to ‘z’ in 1 second
  • Type the character ‘z’ in 1 second
  • Move the pointer clockwise to ‘j’ in 10 seconds
  • Type the character ‘j’ in 1 second
  • Move the pointer clockwise to ‘p’ in 6 seconds
  • Type the character ‘p’ in 1 second
  • Move the pointer anti-clockwise to ‘c’ in 13 seconds.

Подход: Для решения данной проблемы можно выполнить следующие шаги:

  • Рассчитайте время, необходимое для достижения индекса символа от текущего индекса указателя в обоих направлениях:
    • время по часовой стрелке рассчитывается путем взятия абсолютной разницы обоих индексов
    • время против часовой стрелки вычисляется путем вычитания времени по часовой стрелке из 26
  • К ответу добавляется минимум обоих времен, полученных на предыдущем шаге.
  • Затем, чтобы напечатать символ, к ответу также добавляется одна единица времени.

Наконец, выведите полученный ответ за минимально необходимое время.

Ниже приведена реализация вышеуказанного подхода:


Временная сложность: O(N), где N — длина заданной строки str.
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ