1769. 移动所有球到每个盒子所需的最小操作数

题目

在一步操作中，你可以将 一个 小球从某个盒子移动到一个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需满足 abs(i - j) == 1 。注意，操作执行后，某些盒子中可能会存在不止一个小球。

返回一个长度为 n 的数组 answer ，其中 answer[i] 是将所有小球移动到第 i 个盒子所需的 最小 操作数。

每个 answer[i] 都需要根据盒子的 初始状态 进行计算。

 

示例 1：

输入：boxes = "110"
输出：[1,1,3]
解释：每个盒子对应的最小操作数如下：
1) 第 1 个盒子：将一个小球从第 2 个盒子移动到第 1 个盒子，需要 1 步操作。
2) 第 2 个盒子：将一个小球从第 1 个盒子移动到第 2 个盒子，需要 1 步操作。
3) 第 3 个盒子：将一个小球从第 1 个盒子移动到第 3 个盒子，需要 2 步操作。将一个小球从第 2 个盒子移动到第 3 个盒子，需要 1 步操作。共计 3 步操作。

示例 2：

输入：boxes = "001011"
输出：[11,8,5,4,3,4]

 

提示：

• n == boxes.length
• 1 <= n <= 2000
• boxes[i] 为 '0' 或 '1'

分析

就是左右处理一下，规律很明显，在当前下标i下，小于i的往左边移动，大于i的往右边移动。

题解

class Solution {
    public int[] minOperations(String boxes) {
        int l = 0,
                r = 0,
                len = boxes.length(),
                rans = 0,
                lans = 0;
        for (int i = 1; i < len; ++i) {
            if (boxes.charAt(i) == '1') {
                rans += i;
                r++;
            }
        }
        int[] result = new int[len];
        for (int i = 0; i < len; ++i) {
            result[i] = rans + lans;
            rans -= r;
            if (boxes.charAt(i) == '1') l++;
            if (i + 1 < len && boxes.charAt(i + 1) == '1') r--;
            lans += l;
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24