Количество клиентов, способных получить желаемый вкус мороженого

Даны два вкуса мороженого шоколадное и ванильное, обозначенные цифрами 0 и 1 соответственно. Люди стоят в очереди, чтобы получить желаемый вкус мороженого из стопки мороженого.

• Если клиент в начале очереди предпочитает пакет мороженого наверху стопки, он возьмет его и покинет очередь.
• В противном случае они покинут его и перейдут в конец очереди.

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

Даны два массива customer[] и icecream[] , где customer[i] — это предпочтение i -го клиента (i = 0 — начало очереди), а icecream[i] обозначает тип i -го мороженого в стопке. (i =0 — вершина стека). Задача состоит в том, чтобы найти количество клиентов, способных получить желаемый вкус мороженого.

Примеры:

Input: customer = {1, 1, 0, 0}, icecream = {0, 1, 0, 1}
Output: 4
Explanation: Following is the sequence in which customers got their desired flavor of ice cream. 
Front customer leaves top icecream pack and move to end of line . Now customer = {1, 0, 0, 1}.
Front customer leaves top icecream pack and moves to end of line . Now customer  = {0, 0, 1, 1}.
Front customer get icecream and leave line. Now icecream = [1, 0, 1] and customer = {0, 1, 1}.
Front customer leaves top icecream pack and move to end. Now customer = {1, 1, 0} .
Front customer get icecream pack and leaves the line. Now icecream = {0, 1} and customer = {1, 0}.
Front customer leaves line and move to end. Now customer = {0, 1}.
Front customer get icecream pack and leaves line. Now customer = {1} and icecream {1}.
Front customer get icecream pack and now line is empty.
Therefore, all four customer able to get desired icecream pack.

Input: customer = {1, 1, 1, 0, 0, 1}, icecream = {1, 0, 0, 0, 1, 1}
Output: 3

Подход 1: Эту проблему можно решить с помощью стека и очереди. Выполните следующие шаги, чтобы решить данную проблему.

• Создайте стек и поместите в него массив icecream [] .
• Создайте очередь и поместите массив customer[] в очередь
• Инициализируйте переменную, скажем, topRejected=0 , чтобы отслеживать отклоненный элемент.
• Если передняя часть очереди равна верхней части стека , извлеките элементы из стека, удалите элемент из очереди и обновите topRejected=0 .
• В противном случае увеличьте счетчик topRejected и удалите элемент из начала очереди и добавьте его последним.
• Если размер очереди равен topRejected , то прерываем цикл.
• В качестве требуемого ответа выведите icecream.length – queue.size (поскольку оставшийся элемент в очереди не сможет получить желаемую упаковку мороженого).

Временная сложность: O(N)

Вспомогательное пространство: O(N)

Подход 2: Вышеприведенный подход может быть дополнительно оптимизирован, и можно избежать дополнительного пространства O (N). Выполните следующие шаги, чтобы решить данную проблему.

• Сохранение порядка очереди бесполезно.
• Объявите массив, скажем, count[] , который будет отслеживать предпочтения клиентов.
• Увеличить count[0] , если customer[i] равно 0 , иначе увеличить count[1] .
• Теперь инициализируйте k , в котором будет храниться количество клиентов, которые получат желаемую упаковку мороженого.
• Пройдитесь по массиву мороженого и проверьте, возьмет ли кто-нибудь еду из левого клиента.
• Наконец выведите k как окончательный ответ.

Временная сложность: O(N)

Вспомогательное пространство: O(1)