如何计算将长度为N的二进制串转为全0的最少操作次数？

给定长度为N的二进制串，允许选择两个相邻字符，将二者替换为它们的XOR值（即两个字符替换为两个相同的XOR结果，字符串长度保持不变），需找出将该二进制串转为全0的最少操作次数。例如，二进制串"101"经过4次操作可转为全0：选取第1、2位异或得到"111"，再选第1、2位异或得到"001"，接着选第2、3位异或得到"011"，最后选第2、3位异或得到"000"。

以下是你提供的尝试代码：

def checkAllZeros(astr):
    for each_char in astr:
        if each_char == 1:
            return False
    return True


def getMinOperations(astr):
    totalOps = 0
    while checkAllZeros(astr):
        i = 0
        j = 1
        if j < len(astr):
            if (astr[i] == '0' and astr[j] == '1') or (astr[i] == '1' and astr[j] == '0'):
                astr = astr[0:i] + '11' + astr[i + 2:]
                totalOps += 1
            elif astr[i] == '1' and astr[j] == '1':
                astr = astr[0:i] + '00' + astr[i + 2:]
                totalOps += 1
                i += 1
                j += 1
            else:
                i += 1
                j += 1


if __name__ == '__main__':
    print(getMinOperations('1111'))

你的代码存在的问题 #

• 类型判断错误：checkAllZeros中判断each_char == 1，但字符串中的字符是'0'/'1'（字符串类型），应改为each_char == '1'。
• 循环逻辑颠倒：while checkAllZeros(astr)意味着当字符串已经全0时才进入循环，完全反了，正确应为while not checkAllZeros(astr)。
• 遍历逻辑失效：每次循环都重置i=0,j=1，导致每次都从字符串开头重新处理，无法完整遍历整个字符串，容易陷入无限循环或处理不完整。
• 贪心策略局限性：局部最优操作（比如遇到相邻1就消除）无法保证全局最优，对较长字符串无效，需要用动态规划解决。

动态规划解法 #

前提说明 #

只有当二进制串中1的个数为偶数时，才能转为全0（因为每次操作后1的个数的奇偶性要么不变，要么翻转，最终全0是偶数个1，所以原串必须是偶数个1）。

思路定义 #

定义两个状态：

• dp[i][0]：处理前i个字符，使得前i个字符全为0的最少操作次数。
• dp[i][1]：处理前i个字符，使得前i-1个字符全为0，第i个字符为1的最少操作次数。

状态转移方程 #

设第i个字符为ch（对应字符串索引i-1）：

1. 当ch == '0'时：
   • dp[i][0] = min(dp[i-1][0], dp[i-1][1] + 2)：要么前i-1位已经全0，当前位0无需操作；要么前i-1位最后是1，操作这两个位置（1和0）变为11（1次操作），再操作11变为00（第2次操作），总共+2次。
   • dp[i][1] = 无穷大：无法从任何合法状态得到前i-1位全0且第i位为1的状态（当前位是0）。
2. 当ch == '1'时：
   • dp[i][0] = dp[i-1][1] + 1：前i-1位最后是1，当前位也是1，操作这两个1变为00，花费1次操作。
   • dp[i][1] = dp[i-1][0]：前i-1位全0，当前位是1，无需操作直接进入该状态。

实现代码 #

def getMinOperations(s):
    n = len(s)
    INF = float('inf')
    # dp[i][0]：前i个字符全0的最少操作次数
    # dp[i][1]：前i-1个字符全0，第i个字符为1的最少操作次数
    dp = [[INF] * 2 for _ in range(n+1)]
    dp[0][0] = 0
    
    for i in range(1, n+1):
        ch = s[i-1]
        if ch == '0':
            dp[i][0] = min(dp[i-1][0], dp[i-1][1] + 2)
            dp[i][1] = INF
        else:
            dp[i][0] = dp[i-1][1] + 1 if dp[i-1][1] != INF else INF
            dp[i][1] = dp[i-1][0]
    
    # 检查是否有解
    count_ones = s.count('1')
    if count_ones % 2 != 0:
        return -1  # 奇数个1无法转为全0
    return dp[n][0] if dp[n][0] != INF else -1

if __name__ == '__main__':
    print(getMinOperations('101'))  # 输出4，符合示例
    print(getMinOperations('1111')) # 输出2
    print(getMinOperations('1001')) # 输出5

代码解释 #

• 初始化dp数组，用无穷大表示不可达状态。
• 遍历每个字符，根据当前字符是0或1，按照状态转移方程更新dp值。
• 最后检查原串1的个数是否为偶数，若为奇数则返回-1表示无解；否则返回dp[n][0]，即处理完所有字符后全0的最少操作次数。

内容的提问来源于stack exchange，提问作者user1870400