python - 交替 1 和 0 的最小数量

Question

我想找到交替 [0, 1, 0, 1] 所需的最少翻转次数，例如给定 [1, 1, 0, 1]。所以在这种情况下，它是一次翻转。

def solution(A):
    count = 0
    myDict = {}
    myDict[1] = True
    myDict[0] = False

    next = None
    # first element value
    val = myDict[A[0]]
    if val == True:
        next = False
    else:
        next = True

    for element in A[1:]:
        if next != myDict[element]:
            count += 1
            # do something to update element
            myDict[element] = next
        if myDict[element] == True:
            next = False
        else:
            next = True

    return count

我的解决方案不适用于输入 [1, 1, 0, 1, 1]。因为当它应该返回的答案是 2 时它返回 3(将第一个索引和最后一个索引元素更改为 0)。我该如何解决这个问题？

Answer 1

您可以计算每种模式的差异，然后取 min

def minFlip(a):
    return min(
        sum(n == i % 2 for i, n in enumerate(a)),
        sum(n == (i + 1) % 2 for i, n in enumerate(a))
    )

minFlip([1, 1, 0, 1, 1])
#2
minFlip([0, 1, 0, 1, 0])
#0
minFlip([1, 1, 1, 1, 1])
#2
minFlip([0, 0, 0, 0, 0])
#2