0

我正在解决一个LeetCode 问题：将所有球移动到每个盒子的最小操作数。

你有n盒子。你会得到一个长度为 的二进制字符串 box ，如果第一个盒子是空的，则为 '0'，如果它包含一个球，则为 '1 n' boxes[i]。i在一次操作中，您可以将一个球从一个盒子移动到一个相邻的盒子。返回一个大小为 的数组答案n，其中answer[i]是将所有球移动到第ith 个盒子所需的最小操作数。对于输入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）？

谢谢！

4

2 回答 2

2

将left[i]其视为将所有球从 0 开始移动到第 i 个索引的成本。

所以，

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)
于 2021-02-23T04:10:07.937 回答
0

@dunkypie的评论帮助：

“我终于用 DP 建立了对这个问题的直觉。这里是。当我们说计算将一个盒子左边的所有球移动到那个 bax 的操作数时，假设我们在第 i 个位置（或盒子). 这由两部分组成，首先 dp[i - 1] 将为我们提供将所有球移动到第 (i - 1) 个位置的操作次数，现在我们将所有球移动到 (i - 1) ) th position in the (i - 1) th position (or box). 然后下一部分涉及将所有在 (i - 1) th 位置的球移动到 i th 位置。还要注意移动单个球的成本1 个位置是 1。所以递归关系变为：

dp[i] = dp[i - 1] + (1 * balls) 其中 1 是移动单个球的成本。

于 2021-02-24T03:09:20.667 回答