翻转二进制字符串中的位并避免 10 模式

Question

我有一个二进制字符串，其位 0 和 1 的长度为 n。我想以这样的方式翻转从 0 到 1 和 1 到 0 的位，以便存在具有 10 模式的子串。找出所需的最少翻转次数。

示例： 输入 = 10110 输出=2 解释：翻转索引 0 和 4 处的位，因此字符串变为 00111，这里不存在模式 10 的子字符串

限制： 字符串 n 的长度为 1 到 3*10^5

这是我的代码：

static int solve(String s) {
  int n = s.length();
  int flips = 0;
  char[] ar = s.toCharArray();
  for(int i=0; i<n-1; i++) {
      if(ar[i] == '1' && ar[i+1] == '0') {
      flips++;
      ar[i+1]='1'
   }
  }
  return flips;
}

这里我检查模式10，如果发现我将其更改为11。但是这个代码方法不正确，因为我需要找到最小值，那么解决这个问题的正确方法是什么？

Answer 1

您可以使用动态编程，我们存储最少数量的操作来生成有效前缀，直到每个索引都以 0 和 1 结尾。

var minOps = new int[2];
for (char c : s.toCharArray())
    minOps = new int[]{minOps[0] + (c != '0' ? 1 : 0), 
                Math.min(minOps[0], minOps[1]) + (c != '1' ? 1 : 0)};
return Math.min(minOps[0], minOps[1]);