。 K 连续位翻转的最小次数

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

难

给你一个二进制数组 nums 和一个整数 k。

k 位翻转是从 nums 中选择一个长度为 k 的子数组，同时将子数组中的每个 0 变为 1，将子数组中的每个 1 变为 0。

返回所需的k 位翻转 的最小次数，以使数组中不存在 0。如果不可能，则返回-1.

子数组是数组的连续部分。

示例1：

• 输入： nums = [0,1,0], k = 1
• 输出： 2
• 解释： 翻转 nums[0]，然后翻转 nums[2]。

示例2：

• 输入： nums = [1,1,0], k = 2
• 输出： -1
• 解释：无论我们如何翻转大小为 2 的子数组，都不能让数组变成 [1,1,1]。

示例 3：

• 输入： nums = [0,0,0,1,0,1,1,0], k = 3
• 输出： 3
• 说明：

  Flip nums[0],nums[1],nums[2]: nums becomes [1,1,1,1,0,1,1,0]
  Flip nums[4],nums[5],nums[6]: nums becomes [1,1,1,1,1,0,0,0]
  Flip nums[5],nums[6],nums[7]: nums becomes [1,1,1,1,1,1,1,1]

约束：

• 1 5
• 1

解决方案：

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer
     */
    function minKBitFlips($nums, $k) {
        $flipped = array_fill(0, count($nums), false);
        $validFlipsFromPastWindow = 0;
        $flipCount = 0;

        for ($i = 0; $i < count($nums); $i++) {
            if ($i >= $k) {
                if ($flipped[$i - $k]) {
                    $validFlipsFromPastWindow--;
                }
            }
            if ($validFlipsFromPastWindow % 2 == $nums[$i]) {
                if ($i + $k > count($nums)) {
                    return -1;
                }
                $validFlipsFromPastWindow++;
                $flipped[$i] = true;
                $flipCount++;
            }
        }

        return $flipCount;
    }
}

联系链接

• 领英
• GitHub

以上是。 K 连续位翻转的最小次数的详细内容。更多信息请关注PHP中文网其他相关文章！