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

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

Дана строка S размера N , состоящая из «0», «1» и «?», где N всегда четно. Разделите строку на две разные строки, скажем, S1 и S2 , где S1 будет содержать только символы с четными индексами S , а S2 будет содержать только символы с нечетными индексами S . Задача состоит в том, чтобы найти минимально возможные шаги, необходимые для предсказания, какая из двух строк S1 и S2 будет иметь максимальное количество единиц. За один шаг выберите один символ для S1 или S2. Если символ ' 0 ', выберите ' 0 ', если символ ' 1 ', выберите ' 1 ', а если символ ' ? ', затем выберите любой из ' 1 ' или ' 0 '.

Пример:

Input: s = “?10?0?”
Output: 4
Explanation:
Step 1: For S1 character to choose is S[0]=’?’, so choose ‘0’. S1=”0″, S2=””.
Step 2: For S2 character to choose is S[1]=’1′, so choose ‘1’. S1=”0″, S2=”1″.
Step 1: For S1 character to choose is S[2]=’?’, so choose ‘0’. S1=”00″, S2=”1″.
Step 1: For S1 character to choose is S[3]=’?’, so choose ‘1’. S1=”00″, S2=”11″.
After Step 4, S2 will have more number of 1’s  irrespective of what number is chosen for the remaining indexes.

Input: s = “?1?0??0110”
Output:  7

Подход: Идея состоит в том, чтобы решить проблему рекурсивно и ответить на нее после изучения всех возможных результатов. Теперь, чтобы решить эту проблему, выполните следующие действия:

  1. Создайте функцию с именем minSteps , имеющую параметры, строку S , указатель i , который будет указывать на текущее местоположение в строке, до которого строка будет разделена, целые числа count1 и count2 , которые будут хранить количество единиц до i в S1 и S2 соответственно, целые числа first и second для хранения доступных мест в S1 и S2 , для которых не выбрано значение, и целое число n , обозначающее размер строки S . Эта функция вернет минимальные шаги, необходимые для предсказания ответа.
  2. Теперь изначально текущий указатель равен нулю, поэтому i=0 . Поскольку до сих пор значения для S1 и S2 не выбраны, и все места в S1 и S2 доступны для заполнения, поэтому count1=0 , count2=0 , first = n/2 и second=n/2 . Итак, теперь вызовите функцию minSteps с этими аргументами.
  3. При каждом вызове функции minSteps :
    • Проверьте базовые случаи, а именно:
      • Если i достигает n (т.е. i=n ), потому что это означает, что и S1 , и S2 полностью заполнены, и теперь ответ можно определенно предсказать. Итак, верните 0.
      • Если count1 становится больше, чем сумма second и count2, то вернуть 0, потому что теперь, даже после выбора всех доступных мест в S2 , в S1 будет больше единиц.
      • Если count2 становится больше, чем сумма first и count1, то вернуть 0 по причине, указанной выше.
    • После проверки базовых случаев проверьте, является ли i четным или нечетным. Если i четное, то этот индекс выбирается S1 , иначе S2 .
    • Таким образом, уменьшайте первое или второе значение в зависимости от того, какая строка заполняется в данный момент, потому что доступные места в этой строке уменьшатся на одно место после заполнения.
    • Теперь, если текущий символ '?' (т.е. s[i] = '?' ), затем сделайте оба рекурсивных вызова выбора "1" и выбора "0" и верните минимум из двух после добавления к ним 1.
    • В противном случае сделайте один вызов и верните ответ после добавления одного к нему.
  4. Последний рекурсивный вызов даст ответ на этот вопрос.

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

Временная сложность: O(2^N)
Вспомогательное пространство: O(1)

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