Найти наименьшее число, которое не встречается в качестве подпоследовательности строки

Ответ 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"...