995.K连续位的最小翻转次数

链接：995.K连续位的最小翻转次数
难度：Hard
标签：位运算、队列、数组、前缀和、滑动窗口
简介：在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。返回所需的 K 位翻转的最小次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。

题解 1 - typescript

• 编辑时间：2021-02-18
• 执行用时：1580ms
• 内存消耗：46.4MB
• 编程语言：typescript
• 解法介绍：贪心，直接翻转每个 0。

function minKBitFlips(A: number[], K: number): number {
  const checkZero = (v: number) => !(v & 1);
  if (K === 1) return A.filter(checkZero).length;
  const startI = A.findIndex(checkZero);
  if (startI === -1) return 0;
  const flip = (index: number) => {
    for (let i = index, l = index + K; i < l; i++) {
      A[i] ^= 1;
    }
  };
  const len = A.length - K;
  let ans = 0;
  for (let i = startI; i <= len; i++) {
    if (!(A[i] & 1)) {
      ans++;
      flip(i);
    }
  }
  return A.slice(len).every(v => v & 1) ? ans : -1;
}