Задача дня, над которой я решил поработать, была от TopCoder.
Задача 1 из комнаты [SRM 497 DIV 1]: Перестановка подписи.
Проблема
Сигнатура перестановки — это строка, которая вычисляется следующим образом: для каждой пары последовательных элементов перестановки запишите букву «I» (возрастающую), если второй элемент больше первого, в противном случае запишите букву «Д» (убывающая).
Например, подпись перестановки {3,1,2,7,4,6,5} — «DIIDID».
Ваша задача состоит в том, чтобы обратить это вычисление: вам дана строковая подпись, содержащая подпись перестановки. Найдите и верните лексикографически наименьшую перестановку с заданной сигнатурой. Если такой перестановки не существует, вместо этого верните пустой int [].
Мысли
Сначала я не был уверен, как сделать это вручную, и мне пришлось придумать пару простых случаев, чтобы попытаться отработать метод выполнения этого вручную.
Каждый из тестов, которые я перечисляю ниже, был моим прогрессом в том, как я работал над случаями, которые, как я мог придумать, должны были найти различное поведение. Однако дольше всего я застрял на последней строке задачи, поскольку не мог (и до сих пор не могу) придумать сигнатуру в определенном домене, которая не имеет перестановки.
Я попробовал подход «разделяй и властвуй», оценивая каждый подраздел подписи и текущее максимальное значение перестановки. Поскольку в худшем случае, когда нужно знать об остальной части подписи, это не сработает. Вместо этого я решил воспринимать «перестановку» заголовка буквально и сохранить текущий результат по отношению к обработанной подписи по мере продвижения по цепочке.
- Для приращения мне нужно знать только предыдущее самое высокое значение, так как я хочу, чтобы чем меньше значение, тем дальше к началу результата.
- Для уменьшения мне нужно знать, когда предыдущее увеличение или начало подписи, чтобы сдвинуть предыдущий сегмент вверх, обеспечивая наименьшее возможное уменьшение.
С помощью этих двух правил я могу охватить все возможные случаи, о которых только мог подумать.
Решение
Тесты
- Просто увеличить: «II» -> { 1, 2, 3
- Просто уменьшить: "DD" -> { 3, 2, 1
- Альтернативный одиночный "IDI" -> { 1, 3, 2, 4
- Подпись с одним типом, охватывающим несколько смежных областей другого
- IDDI -› { 1, 4, 3, 2, 5
- "DIID" -> { 2, 1, 3, 5, 4
- Гарантирует, что вы не просто оглядываетесь назад
Код
Как всегда, я хотел бы критики с моими мыслями