DEV Community
·
1769. 将所有球移动到每个盒子的最小操作次数
💡
原文英文，约800词，阅读约需3分钟。
📝
内容提要
给定一个二进制字符串表示的盒子，使用前缀和方法通过左右两次遍历高效计算将所有球移动到每个盒子所需的最小操作次数，时间复杂度为O(n)。
🎯
关键要点
- 给定一个二进制字符串表示的盒子，盒子中'0'表示空，'1'表示有球。
- 每次操作可以将一个球从一个盒子移动到相邻的盒子。
- 返回一个数组，表示将所有球移动到每个盒子所需的最小操作次数。
- 可以使用前缀和方法，通过左右两次遍历高效计算操作次数，时间复杂度为O(n)。
- 左到右遍历计算从左侧移动球到当前盒子的操作次数。
- 右到左遍历计算从右侧移动球到当前盒子的操作次数。
- 每个盒子的总操作次数是左右遍历结果的总和。
- 示例1：输入'110'，输出[1,1,3]。
- 示例2：输入'001011'，输出[11,8,5,4,3,4]。
- 空间复杂度为O(n)，因为需要存储结果数组。
➡️
