。 K 個の連続するビット反転の最小数

995。 K 個の連続ビット反転の最小数

ハード

バイナリ配列 nums と整数 k が与えられます。

k ビットの反転は、nums から長さ k の部分配列を選択し、同時に部分配列内のすべての 0 を 1 に変更し、部分配列内のすべての 1 を 0 に変更します。

配列内に 0 が存在しないようにするために必要な k ビット 反転の最小数を返します。不可能な場合は、-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;
    }
}

連絡先リンク

• LinkedIn
• GitHub

以上が。 K 個の連続するビット反転の最小数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。