Я решаю 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
)?
Благодарю вас!
i
к индексуi+1
увеличивает количество операций для каждого шара слева. Значит, если слеваcount
шаров, то общее количество операций увеличивается наcount
. - person user3386109   schedule 23.02.2021