小葱有一面由 块砖排成一行形成的墙,砖块有黑白两种颜色。 小葱心目中的墙是黑白两种砖块交替构成的,于是她要把现在的墙进行改造。 每一次修改可以把任意一块砖块的颜色反转(即白变黑或黑变白),请你帮小葱算算至少需要多少次修改才能把现在的墙修改为小葱心目中的墙。用吃++实现的代码
时间: 2023-05-27 11:07:36 浏览: 29
思路:
遍历整个墙,分别计算将该位置的砖块染成黑色和染成白色所需要的修改次数,取两者中的最小值作为该位置的最小修改次数。
代码实现:
```
def minModify(wall):
n = len(wall)
m = len(wall[0])
cnt = [[0, 0] for _ in range(m)] # 统计每列黑白砖块数量
for i in range(n):
for j in range(m):
cnt[j][wall[i][j]] += 1
res = float("inf")
for i in range(m):
cur = 0
for j in range(m):
if j % 2 == 0:
cur += cnt[j][1] # 奇数列变成黑色
else:
cur += cnt[j][0] # 偶数列变成白色
res = min(res, cur)
cur = 0
for j in range(m):
if j % 2 == 0:
cur += cnt[j][0] # 奇数列变成白色
else:
cur += cnt[j][1] # 偶数列变成黑色
res = min(res, cur)
return res
```
时间复杂度:$O(nm)$
空间复杂度:$O(m)$