Реализация Удаление соседних номеров из стека, сколько осталось?

Question

Предположим, у нас есть стек с n числами, и если 3 или более смежных числа равны, то эти числа могут быть удалены (числа удаляются сверху вниз). Поскольку это стек, у нас есть нормальные операции push(), pop(), top(), и мы знаем n. Кроме того, у меня есть пустой стек и O(1) дополнительное пространство памяти. Существует ли линейный алгоритм для определения количества оставшегося числа? Если да, что бы это было?

Answer 1

Если постоянная область памяти равна как минимум N, то наивный подход уже линейный:)

То есть, учитывая P = предыдущее значение (инициализировано в бесконечность) и C = счетчик (инициализировано в 0):

1. Вытеснение элемента E из стека
2. Если E = P, приращение C, в противном случае установите C в 1.
3. Если C> = 3, продолжайте выталкивать элементы, перезаписывая E, отключить второй стек до тех пор, пока E = / = P
4. Вставить E. во второй стек.
5. Повторять с 1 до тех пор, пока первый стек не станет пустым, а затем вытолкнуть и нажать все значения из tempвернитесь к оригиналу, увеличивая счетчик для каждого числа, как и вы.

Answer 2

Идея довольно проста.Мы просто перемещаем записи в другой стек и подсчитываем, сколько мы будем удалять.Для этого мы отслеживаем последний элемент и сколько раз его видели:

lastElement = ∅      //no last element
lastElementSeen = 0  //how many times did the last element occur in succession
totalRemoved = 0     //how many elements would we remove?
while(!stack.empty)
    element = stack.top
    stack.pop()
    otherStack.push(element)
    if element == lastElement
        lastElementSeen++
    else
        if lastElementSeen >= 3
            totalRemoved += lastElementSeen
        lastElement = element
        lastElementSeen = 1

Вы также можете фактически удалить элементы из других стеков, а не просто считать их.Вы также можете не помещать их в другой стек, если они вам больше не нужны.