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

博主： zhaojun
发布时间：2023 年 01 月 25 日
1055 次浏览
暂无评论
840字数
分类：默认分类

https://leetcode.cn/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/description/

## 题目

有 `n` 个盒子。给你一个长度为 `n` 的二进制字符串 `boxes` ，其中 `boxes[i]` 的值为 `'0'` 表示第 `i` 个盒子是 **空** 的，而 `boxes[i]` 的值为 `'1'` 表示盒子里有 **一个** 小球。

在一步操作中，你可以将 **一个** 小球从某个盒子移动到一个与之相邻的盒子中。第 `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'`

## 思路

### 双重循环法

这个就是直觉上最简单的办法，第一次循环为目的地，第二次循环为计算所有小球转移到目的地的最小操作数，最后返回结果，不过这个方法时间复杂度为 $O(n^2)$

### 根据前一个盒子的操作数，计算当前盒子的操作数

如盒子 `[0,0,1,0,1,1]` ，下标为 3 时，左侧 1 的数量为 1 个，右侧 1 的数量为 2 个。总计操作数为 1 + 1 + 2 个，也就是 4。
当下标为 4 时，所有左侧 1 的盒子都要多移动 1 步才能到当前盒子，所有右侧为 1 的盒子都可以减少 1 步到当前盒子。
所有左侧盒子多移动一步，那就看多少个盒子，就加多少个。
所有右侧盒子少移动一步，那就看多少个盒子，就减多少个。
所以可以得出 `answer[i] = answer[i - 1] + left - right`

![2023-01-25T04:02:54.png][1]

图片来源： https://leetcode.cn/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/solutions/2001791/-by-muse-77-ilaz/

## 代码

### 双重循环法
```java
class Solution {
    public int[] minOperations(String boxes) {
        int[] answer = new int[boxes.length()];
        for (int i = 0; i < boxes.length(); i++) {
            int sum = 0;
            for (int j = 0; j < boxes.length(); j++) {
                char c1 = boxes.charAt(j);
                if (c1 == '1') {
                    sum += Math.abs(i - j);
                }
            }
            answer[i] = sum;
        }
        return answer;
    }
}
```

### 动态计算法

```java
class Solution {
    public int[] minOperations(String boxes) {
        int[] answer = new int[boxes.length()];
        int left = boxes.charAt(0) - '0', right = 0, n = boxes.length();
        for (int i = 1; i < n; i++) {
            if (boxes.charAt(i) == '1') {
                right++;
                answer[0] += i;
            }
        }

for (int i = 1; i < n; i++) {
            answer[i] = answer[i - 1] + left - right;
            if (boxes.charAt(i) == '1') {
                left++;
                right--;
            }
        }

return answer;
    }
}
```

[1]: https://zhaojun.vip/usr/uploads/2023/01/3208550401.png

最后修改：2023 年 01 月 25 日

如果觉得我的文章对你有用，请我喝杯咖啡吧。

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

天天下载
学习了，谢谢 http://appdo...
聊应用
来留个脚印。
快帆云
你好，我们的机场：快帆云，已经稳定运营三年多，现在诚邀推广员。...
在nginx层面给任意项目站点增加访问限制：casdoor+oauth2-proxy - Blog By chenchen.site
[...]如果是宝塔用户可以直接使用以下方法安装模块，参考文章...
大概
你好，我就想整一个网盘，用作知识付费，就是普通用户只可以看到标...

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

zhaojun • 2023 年 01 月 25 日

https://leetcode.cn/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/description/

## 题目

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

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

**示例 1：**

**示例 2：**

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

**提示：**

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

## 思路

### 双重循环法

### 根据前一个盒子的操作数，计算当前盒子的操作数

![2023-01-25T04:02:54.png][1]

图片来源： https://leetcode.cn/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/solutions/2001791/-by-muse-77-ilaz/

## 代码

### 动态计算法

for (int i = 1; i < n; i++) {
            answer[i] = answer[i - 1] + left - right;
            if (boxes.charAt(i) == '1') {
                left++;
                right--;
            }
        }

return answer;
    }
}
```

[1]: https://zhaojun.vip/usr/uploads/2023/01/3208550401.png

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

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

谈裸辞和开源的体会

剑指 Offer 04. 二维数组中的查找

Shiro 学习 04 - 加密

通过 Github Actions 自动构建 ZFile 镜像并推送到 Docker Hub

优化 Java 项目 Docker 镜像内存占用从 500 M 到 100M

leetcode 005 最长回文子串

巧用 MyBatis 构建树形结构

阿里云 Centos7.x 安装 Oracle 11g 详细过程

代码命名之 Spring

VIM 常用操作

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

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

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

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款