Интуиция за вычислением сумм префиксов и суффиксов

Я решаю LeetCode Вопрос: Минимальное количество операций для перемещения всех шаров в каждую коробку.

У вас есть n ящиков. Вам даны бинарные строковые ящики длины n, где boxes[i] равно '0', если iй ящик пуст, и '1', если он содержит один шар. За одну операцию вы можете переместить один шар из коробки в соседнюю коробку. Возвращает ответ в виде массива размером n, где answer[i] — минимальное количество операций, необходимых для перемещения всех шаров в i-й ящик. Для входа boxes = "001011" выход: [11,8,5,4,3,4].

Делать это в O(n^2) тривиально. Я мог решить это только так. Я пытаюсь понять это O(n) решение, но с трудом:

class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();

        int[] left = new int[n];
        int[] right = new int[n];
        int[] ans = new int[n];

        int count = boxes.charAt(0) - '0';
        for(int i = 1 ; i < n ; i++){
            left[i] = left[i - 1] + count;
            count += boxes.charAt(i) - '0';
            // System.out.println("i: "+i+" left[i]: "+left[i]+" left[i-1] : "+left[i-1]+" count: " + count);
        }

        count = boxes.charAt(n - 1) - '0';
        for(int i = n - 2 ; i >=0 ; i--){
            right[i] = right[i + 1] + count;
            count += boxes.charAt(i) - '0';
            // System.out.println("i: "+i+" right[i]: "+right[i]+" right[i+1] : "+right[i+1]+" count: " + count);
        }
        
        for(int i = 0 ; i < n ; i++) {
            ans[i] = left[i] + right[i];
        }

        return ans;
    }
}

Может кто-нибудь уточнить логику:

left[i] = left[i - 1] + count;
count += boxes.charAt(i) - '0';

Я понимаю, что мы увеличиваем count всякий раз, когда сталкиваемся с шаром, но как left[i] = left[i - 1] + count; помогает нам подсчитать количество операций, необходимых до сих пор, чтобы переместить все шары слева в i (и наоборот в случае right)?

Благодарю вас!


person P.K.    schedule 23.02.2021    source источник
comment
Основная идея состоит в том, что переход от индекса i к индексу i+1 увеличивает количество операций для каждого шара слева. Значит, если слева count шаров, то общее количество операций увеличивается на count.   -  person user3386109    schedule 23.02.2021


Ответы (2)


Думайте о left[i] как о стоимости перемещения всех шаров, начиная с 0 до i-го индекса.

So,

left[i] = 
  left[i - 1]  (cost to move all 1's to (i - 1) the index) 
  + count      (this is the total number of 1's which will all need to be moved to the ith index so, its cost is count)
person hashmap    schedule 23.02.2021