Задача дня, над которой я решил поработать, была от TopCoder.
Задача 1 из комнаты [SRM 497 DIV 1]: Перестановка подписи.

Проблема

Сигнатура перестановки — это строка, которая вычисляется следующим образом: для каждой пары последовательных элементов перестановки запишите букву «I» (возрастающую), если второй элемент больше первого, в противном случае запишите букву «Д» (убывающая).

Например, подпись перестановки {3,1,2,7,4,6,5} — «DIIDID».

Ваша задача состоит в том, чтобы обратить это вычисление: вам дана строковая подпись, содержащая подпись перестановки. Найдите и верните лексикографически наименьшую перестановку с заданной сигнатурой. Если такой перестановки не существует, вместо этого верните пустой int [].

Мысли

Сначала я не был уверен, как сделать это вручную, и мне пришлось придумать пару простых случаев, чтобы попытаться отработать метод выполнения этого вручную.

Каждый из тестов, которые я перечисляю ниже, был моим прогрессом в том, как я работал над случаями, которые, как я мог придумать, должны были найти различное поведение. Однако дольше всего я застрял на последней строке задачи, поскольку не мог (и до сих пор не могу) придумать сигнатуру в определенном домене, которая не имеет перестановки.

Я попробовал подход «разделяй и властвуй», оценивая каждый подраздел подписи и текущее максимальное значение перестановки. Поскольку в худшем случае, когда нужно знать об остальной части подписи, это не сработает. Вместо этого я решил воспринимать «перестановку» заголовка буквально и сохранить текущий результат по отношению к обработанной подписи по мере продвижения по цепочке.

  • Для приращения мне нужно знать только предыдущее самое высокое значение, так как я хочу, чтобы чем меньше значение, тем дальше к началу результата.
  • Для уменьшения мне нужно знать, когда предыдущее увеличение или начало подписи, чтобы сдвинуть предыдущий сегмент вверх, обеспечивая наименьшее возможное уменьшение.

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

Решение

Тесты

  1. Просто увеличить: «II» -> { 1, 2, 3
  2. Просто уменьшить: "DD" -> { 3, 2, 1
  3. Альтернативный одиночный "IDI" -> { 1, 3, 2, 4
  4. Подпись с одним типом, охватывающим несколько смежных областей другого
  • IDDI -› { 1, 4, 3, 2, 5
  • "DIID" -> { 2, 1, 3, 5, 4
  • Гарантирует, что вы не просто оглядываетесь назад

Код

Перестановка подписи

Как всегда, я хотел бы критики с моими мыслями