题目:
有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes ，其中 boxes[i] 的值为 '0' 表示第 i 个盒子是 空 的，而 boxes[i] 的值为 '1' 表示盒子里有 一个 小球。
在一步操作中，你可以将 一个 小球从某个盒子移动到一个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需满足 abs(i - j) == 1 。注意，操作执行后，某些盒子中可能会存在不止一个小球。
返回一个长度为 n 的数组 answer ，其中 answer[i] 是将所有小球移动到第 i 个盒子所需的 最小 操作数。
每个 answer[i] 都需要根据盒子的 初始状态 进行计算。
官方给出的直接模拟操作的解，Python3, Java, C#, C, C++, Javascript, Go在O(n**2)的时间复杂度下均能通过，唯独Ruby过不了。然而数据规模也只到2000*2000。
如下是Ruby O(n**2)的解法：
def min_operations(boxes)
ans = []
for i in 0...boxes.length
temp = 0
for j in 0...boxes.length
if j != i and boxes[j] == "1"
temp += (j-i).abs
end
end
ans.push(temp)
end
ans
end
上面的代码无法通过，无赖只能使用O(n)的解法，如下所示：
def min_operations(boxes)
left,right,operations = boxes[0].to_i,0,0
for i in 1...boxes.length
if boxes[i] == '1'
right += 1
operations += i
end
end
res = [operations]
for i in 1...boxes.length
operations += left - right
if boxes[i] == '1'
left += 1
right -= 1
end
res.push(operations)
end
res
end
上面的代码才能通过。
