使二进制字符串全部为1的最少两次或三次翻转次数

Question

我刚刚完成了一次编码面试，面试中的一个问题让我很困惑。虽然测试已经结束，但我仍然很想知道如何解决这个问题。

问题：给定一个二进制字符串(仅包含"1"或"0"(，找到获得所有"1"s的二进制字符串所需的最小翻转次数。

执行翻转时，该索引处的值将从"0"变为"1"或从"1"变为"0"

唯一允许你进行的翻转是双翻或三翻。这意味着当执行翻转时，必须在两个或三个相邻索引上执行

示例：

• 对于二进制字符串"1010"，所需的最小翻转次数为2。CCD_ 9＝>CCD_ 10＝>"1111"(完(
• 对于"10001"，所需的最小翻转次数为1。CCD_ 13＝>"11111"(完(

Answer 1

您可以通过对前2/3个字符执行翻转并将递归的结果添加到下一个位置来使用递归强行执行：

def minFlips(s):
if "0" not in s:      return 0  # all 1s, no flip needed
if s in ("00","000"): return 1  # last flip for whole string

def flip(n): # flip 1st n bits
return s[:n].translate({48:49,49:48})+s[n:]

result = [float('inf')] # track minimum flips
if s.startswith("0"):   # must flip if starting with a zero
if len(s)>2:        # first 2 + recursion
result.append(1+minFlips(flip(2)[1:])) 
if len(s)>3:        # first 3 + recursion
result.append(1+minFlips(flip(3)[1:])) 
else: # starts with "1"
result.append(minFlips(s[1:])) # 0 flip + recursion
if "0" in s[:2]: # can flip zero at 2nd position
result.append(1+minFlips(flip(2))) # first 2 + recursion
if "0" in s[:3]: # can flip zero at 2nd or 3rd position
result.append(1+minFlips(flip(3))) # first 3 + recursion
return min(result)
print(minFlips("1010"))       # 2
print(minFlips("10001"))      # 1
print(minFlips("1010110101")) # 4

要优化此功能，可以使用内存化，或添加@lru_cache()装饰器(来自functools(