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

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

class Solution(object):
    def minOperations(self, boxes):
        n = len(boxes)
        operations = [0] * n

        for i in range(n):
            for j in range(n):
                if boxes[j] == '1':
                    operations[i] += abs(j - i)

        return operations

Метод 2: префиксная сумма
Метод префиксной суммы помогает оптимизировать метод грубой силы путем предварительного вычисления совокупной суммы всех операций. Таким образом, мы можем рассчитать количество операций для каждого блока, вычитая сумму префикса в начальном индексе из суммы префикса в конечном индексе. Вот пример кода:

class Solution(object):
    def minOperations(self, boxes):
        n = len(boxes)
        operations = [0] * n
        prefix_sum = [0] * n

        for i in range(n):
            prefix_sum[i] = prefix_sum[i-1] + int(boxes[i])

        for i in range(n):
            for j in range(n):
                if boxes[j] == '1':
                    operations[i] += abs(j - i)

        return operations

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

class Solution(object):
    def minOperations(self, boxes):
        n = len(boxes)
        operations = [0] * n
        total_operations, curr_operations = 0, 0

        for i in range(n):
            total_operations += curr_operations
            if boxes[i] == '1':
                curr_operations += 1

        for i in range(n):
            operations[i] = total_operations
            if boxes[i] == '1':
                total_operations -= 1
                curr_operations += 1

        return operations