- 作者： 负雪明烛
- id： fuxuemingzhu
- 公众号：每日算法题
- 本文关键词：LeetCode，力扣，算法，算法题，交替合并字符串，Merge Strings Alternately，刷题群
目录
题目地址：https://leetcode-cn.com/problems/merge-strings-alternately/
题目描述
有 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.length1 <= n <= 2000-
boxes[i]为 ‘0’ 或 ‘1’
解题思路
暴力
本题的数据规模为 2000，用 O ( N 2 ) O(N^2) O(N2) 的解法竟然能过。这个方法比较简单，直接对每个位置向左右两边统计具体各个 1 的位置之和。
Python 代码如下：
class Solution:
def minOperations(self, boxes: str) -> List[int]:
N = len(boxes)
res = [0] * N
for i in range(N):
left = [i - j for j in range(i) if boxes[j] == "1"]
right = [j - i for j in range(i + 1, N) if boxes[j] == "1"]
res[i] = sum(left) + sum(right)
return res
动态规划
这个才是我在周赛上提交的代码，时间复杂度是 O ( N ) O(N) O(N)，运行时间是上面 O ( N 2 ) O(N ^ 2) O(N2)代码的 1 / 100 1/ 100 1/100。
这个思路是：我们先找到把所有的 1 移到下标为 0 的起始位置需要的最小操作数为 r e s [ 0 ] res[0] res[0]。然后其余把所有 1 移到 i i i 位置的操作数 = 把所有 1 移到 i − 1 i - 1 i−1 位置的的操作数 -（右边的所有 1） + （左边的所有 1），即转移方程是：
r e s [ i ] = r e s [ i − 1 ] − ( o n e s − v i s i t e d ) + v i s i t e d res[i] = res[i - 1] - (ones - visited) + visited res[i]=res[i−1]−(ones−visited)+visited
原理是什么呢？因为把所有位置移动到 r e s [ i ] res[i] res[i] 位置相对于 r e s [ i − 1 ] res[i - 1] res[i−1] 位置来说，所有它右边位置的 1 少移动了一次，它左边位置的 1 多移动了一次。
时间复杂度： O ( N ) O(N) O(N)，空间复杂度： O ( 1 ) O(1) O(1).
class Solution:
def minOperations(self, boxes: str) -> List[int]:
N = len(boxes)
start = 0
ones = 0
for i, box in enumerate(boxes):
if box == "1":
start += i
ones += 1
res = [0] * N
visited = 0
for i in range(len(boxes)):
if i == 0:
res[0] = start
else:
res[i] = res[i - 1] - (ones - visited) + visited
if boxes[i] == "1":
visited += 1
return res
欢迎加入组织
算法每日一题是个互相帮助、互相监督的力扣打卡网站，其地址是 https://www.ojeveryday.com/
想加入千人刷题群的朋友，可以复制上面的链接到浏览器，然后在左侧点击“加入组织”，提交力扣个人主页，即可进入刷题群。期待你早日加入。
欢迎关注我的公众号：每日算法题
日期
2021 年 2 月 21 日 —— 好久不打周赛了，发现手已经非常生。