. Bilangan Minimum K Balikan Bit Berturut-turut

995. Bilangan Minimum K Balikan Bit Berturut-turut

Sukar

Anda diberi nombor tatasusunan binari dan integer k.

Selidikan k-bit sedang memilih subarray panjang k daripada nums dan pada masa yang sama menukar setiap 0 dalam subarray kepada 1, dan setiap 1 dalam subarray kepada 0.

Kembali bilangan minimum k-bit flip diperlukan supaya tiada 0 dalam tatasusunan. Jika tidak boleh, kembalikan -1.

Subarray ialah bahagian bersebelahan daripada tatasusunan.

Contoh 1:

• Input: nombor = [0,1,0], k = 1
• Output: 2
• Penjelasan: Balikkan nombor[0], kemudian balikkan nombor[2].

Contoh 2:

• Input: nombor = [1,1,0], k = 2
• Output: -1
• Penjelasan: Tidak kira bagaimana kita menyelak subarray bersaiz 2, kita tidak boleh menjadikan tatasusunan menjadi [1,1,1].

Contoh 3:

• Input: nombor = [0,0,0,1,0,1,1,0], k = 3
• Output: 3
• Penjelasan:

  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]

Kekangan:

1 <= nums.length <= 10
• 5
1 <= k <= nums.length

Penyelesaian:

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;
    }
}
Pautan Kenalan



LinkedIn

GitHub



          

            
  

            
        
Atas ialah kandungan terperinci . Bilangan Minimum K Balikan Bit Berturut-turut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!