Я пытаюсь выполнить задание 30 days of coding на python, и в этой статье я буду вычислять количество дней, после которых ни одно растение не умрет.

Конечно, тюльпаны не ядовиты, но мне пришлось позлорадствовать над этой удивительной фотографией, которую я сделал в прошлом году.

Предварительное резюме:

Стеки

Стек — это структура данных в информатике, которая следует принципу «последним пришел — первым вышел» (LIFO). Это означает, что последний элемент, добавленный в стек, удаляется первым. Это похоже на стопку предметов в реальной жизни, например, на стопку тарелок, где вы можете получить доступ только к самой верхней тарелке, а чтобы получить доступ к нижним, вам нужно удалить тарелки сверху.

В Python стеки можно легко реализовать с помощью списков, используя метод append() для добавления элементов в верхнюю часть стека и метод pop() для удаления верхнего элемента.

Вот пример простого стека в Python:

stack = []

# Push elements onto the stack
stack.append(1)
stack.append(2)
stack.append(3)

# Top element of the stack
top_element = stack[-1]

# Pop elements from the stack
popped_element = stack.pop()  # removes and returns the top element (3)

Стеки полезны в различных сценариях программирования, таких как:

  1. Вычисление выражений в языках программирования (например, арифметических выражений или вызовов функций).
  2. Обход древовидных или графовых структур с использованием алгоритмов поиска в глубину.
  3. Внедрение алгоритмов возврата, когда вам нужно вернуться к предыдущему шагу после изучения пути.
  4. Управление вызовами функций и их соответствующими адресами возврата в стеке вызовов программы.

Основные операции, выполняемые со стеком, — это push (добавление элемента на вершину стека) и pop (удаление верхнего элемента). Эти операции обычно выполняются в постоянное время, что делает стеки эффективными для задач, где вам нужно поддерживать определенный порядок и быстро получать доступ к самым последним элементам.

Подробнее об алгоритме DFS:

https://medium.com/@tudorache.a.bogdan/day-10-adjacent-list-roads-and-libraries-1422c8742ac5

Проблема:



Ядовитые растения | HackerRank
Найдите количество дней, через которое погибнут все растения, при условии, что ценность пестицидов для растения больше, чем для…www.hackerrank.com



Решение:

def poisonousPlants(plants):
    days = 0
    stack = []

    for plant in plants:
        days_to_die = 1
        
        # Check if the current plant has more pesticide than the plant on its left
        while stack and plant <= stack[-1][0]:
            _, prev_days_to_die = stack.pop()
            days_to_die = max(days_to_die, prev_days_to_die + 1)

        # If the stack is not empty, it means the current plant dies at some point
        if stack:
            days = max(days, days_to_die)
        else:
            days_to_die = 0

        stack.append((plant, days_to_die))

    return days

Объяснение:

  1. Инициализируйте переменную days, чтобы хранить максимальное количество дней, в течение которых растения больше не будут умирать. Сначала установите его на 0.
  2. Создайте пустой стек для хранения пар (plant_pesticide, days_to_die) для каждого растения.
  3. Повторите список растений.
  4. Установите начальное значение days_to_die равным 1 для текущего завода. Это будет обновлено позже на основе сравнения с растениями слева.
  5. Проверьте, содержит ли текущее растение больше пестицидов, чем растение слева, используя цикл while. Вершина стека представляет растение слева от текущего растения. Если уровень пестицидов текущего растения меньше или равен уровню растения слева от него, мы извлекаем левое растение из стека и обновляем значение days_to_die для текущего растения.
  6. Если стек не пуст после цикла while, это означает, что текущее растение в какой-то момент умрет, и мы обновляем переменную days, чтобы сохранить максимальное количество дней между предыдущим максимумом и значением days_to_die. для действующего завода.
  7. Если стек пустой послецикла while, это означает, что текущее растение не погибнет, так как его уровень пестицидов ниже или равен уровню всех растений слева от него. Итак, мы устанавливаем days_to_die на 0 для текущего завода.
  8. Поместите текущее растение (с его уровнем пестицида и значением days_to_die) в стек.
  9. После завершения цикла, перебирающего все растения, верните переменную days в качестве окончательного ответа.

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

Заключение:

Предоставленное решение задачи о ядовитых растениях является эффективным, поскольку оно имеет линейную временную сложность O(n), где n — количество растений. Это достигается за счет использования структуры данных стека и одного цикла, который перебирает список растений.

Эффективность этого решения обусловлена ​​следующими причинами:

  1. Один проход по списку растений. Алгоритм выполняет итерацию по списку растений только один раз. На каждом этапе он обрабатывает текущий объект и соответствующим образом обновляет стек, обеспечивая сканирование всего массива за один проход.
  2. Операции стека с постоянным временем. Операции добавления и извлечения в стеке имеют постоянную временную сложность, O(1), что позволяет алгоритму эффективно обрабатывать растения и обновлять их дни, чтобы они умерли.
  3. Умное использование стека: в стеке хранятся пары (plant_pesticide, days_to_die), что помогает отслеживать оставшиеся растения и дни их гибели. Это позволяет алгоритму быстро определить, умрет ли растение, и соответственно обновить дни без необходимости в дополнительной структуре данных или более сложной логике.
  4. Нет дополнительных структур данных. Алгоритм не требует никаких других структур данных, кроме стека. Это снижает нагрузку на память и повышает общую эффективность решения.
  5. Нет вложенных циклов. Внутренний цикл while выполняется только тогда, когда уровень пестицидов на текущем растении меньше или равен уровню растения слева от него (которое находится на вершине стека). В этом случае внутренний цикл извлекает элементы из стека до тех пор, пока не будет найдена подходящая позиция для текущего объекта. Поскольку каждое растение добавляется в стек не более одного раза и каждое растение извлекается из стека не более одного раза, общее количество операций во внутреннем цикле равно O(n) на всех итерациях внешнего цикла.

Сочетание этих факторов делает это решение эффективным и оптимальным подходом к решению проблемы ядовитых растений.

Богдан Тудораче | Основатель @berrynews.org

Если вам понравилась статья и вы хотите меня поддержать, сделайте следующее:

  • 👏 Аплодируйте истории (50 хлопков), чтобы эта статья попала в топ
  • 🔔 Подпишитесь на меня в Среднем
  • 📰 Дополнительные материалы по кодированию на Coding Challenge
  • 🔔 Подключиться со мной: LinkedIn| Реддит