。 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中文網其他相關文章！