Ответ 1
Структуры данных, необходимые для этого алгоритма:
- массив битов, один бит для каждого элемента входной строки (и еще один пустой набор бит в конце), один бит на цифру (размер каждого битового набора равен 10)
- 10 стопок позиций - для каждой цифры (необязательно)
- counter (для подсчета цифр в ответе)
Алгоритм:
- Отсканируйте строку ввода назад, нажмите текущую позицию в стек, соответствующую цифре в этой позиции, скопируйте бит из предыдущей позиции и установите бит, соответствующий значению в текущей позиции. Когда все биты в текущем битете установлены, увеличивайте счетчик и очищайте биты.
- Если счетчик все еще равен нулю, получите младший бит в текущем битете и используйте одну цифру, соответствующую этому биту, чтобы построить результирующее число.
- Если единственным несоответствующим битом является "ноль", результирующее число создается как "10", за которым следует результат шага 4 (где предварительно задана начальная цифра "0" ).
- Получите наименьший значащий нулевой бит в текущем битете (но когда этот шаг выполняется в первый раз, проигнорируйте бит, соответствующий "0" ), используйте его как следующую цифру результата, поместите стек, соответствующий этой цифре ( пока вы не получите позицию не ниже текущей позиции), и установите текущую позицию в индекс из этого стека плюс один. Получите битсет, соответствующий текущей позиции, и повторите шаг 4. Этот шаг должен быть выполнен "счетчик + 1" раз или до тех пор, пока не попытается поместить пустой стек.
Альтернативный алгоритм:
Другой альтернативой является перенос большинства вычислений с шага 4 на шаг 1. В этом случае вместо массива биттетов и 10 стеков нам нужны еще более простые структуры данных.
Объяснение и пример:
Шаг 1 этого алгоритма определяет кратчайший суффикс, который содержит любое одноразрядное число в качестве подпоследовательности. Затем он находит самую короткую подстроку, смежную с этим суффиксом, которая также содержит любое одноразрядное число. Вместе они дают кратчайший суффикс, который содержит любое двузначное число. Этот процесс продолжается для 3-значных, 4-значных суффиксов и т.д. Также этот этап предварительной обработки определяет, какие цифры могут быть записаны слева от этих n-значных чисел, так что соответствующая подпоследовательность существует в некотором суффиксе входной строки (эта информация содержится в битах).
Например, для строки ввода 12345678901 этот шаг определяет, что суффикс, начинающийся с индекса "1" , содержит любое возможное одноразрядное число. Также он заполняет биты следующим образом:
index: bitset:
10 0000000010
9 0000000011
8 1000000011
7 1100000011
6 1110000011
5 1111000011
4 1111100011
3 1111110011
2 1111111011
1 0000000000
0 0000000010
Шаги 2,3 касаются некоторых угловых случаев.
Шаг 4 начинается с проверки бита в позиции "0", чтобы найти наименьшую возможную стартовую цифру. В нашем примере устанавливается бит "1" , что означает, что мы не можем запустить наше двузначное число с "1" (все такие числа уже находятся в строке). Также мы не можем запустить его с "0". Следующий бит unset равен "2" , поэтому мы начнем номер с "2" .
Мы могли бы использовать соответствующий стек или просто последовательно искать строку, чтобы перейти к позиции первой цифры "2" . Оставшаяся цифра нашего номера должна быть в суффиксе, начиная с цифры "2" . Бицепс в исходном положении этого суффикса - "1111111011", что означает, что в этом суффиксе используется только неиспользованная цифра "2" . Мы должны остановиться здесь, потому что "counter + 1" равен 2, и мы просто использовали до 2 итераций шага 4. Таким образом, ответ "22".
Вот еще один алгоритм с временной сложностью O(answer + length of the string).
Для каждой цифры (от 0 до 9) подготавливайте массив индексов, где каждый индекс указывает на ближайшую цифру в данной позиции или вправо. Например:
For string 216989210...
and digit "1": 11777777...
Это может быть реализовано путем сканирования массива ввода назад, и как только мы увидим соответствующую цифру, начните записывать свой индекс в индексный массив. Для примера выше это означает, что мы видим самую правую цифру "1" в позиции 7 и заполняем массив индексов 7, пока не увидим другое появление цифры "1" в индексе 1. Затем мы заполняем оставшиеся позиции этим индексом.
Теперь мы можем легко уменьшить сложность алгоритма, упомянутого в OP от O(answer * length of the string) до O(answer + length of the string). Просто следуйте ссылке, предоставленной одним из массивов индексов, чтобы получить ближайшую позицию следующей цифры в текущем номере.
Например, мы могли бы попробовать первые 61 неотрицательные числа, затем для числа "61" мы проверим индексный массив для "6" в первой позиции, чтобы найти индекс "2" (это не обязательно, так как этот индекс уже находится при обработке "60" ), затем мы проверяем индексный массив для "1" в следующей позиции (2 + 1), чтобы найти индекс "7". Это означает, что "61" встречается в заданной строке, и мы можем продолжить "62"...