. Mindestanzahl von K aufeinanderfolgenden Bitwechseln

995. Mindestanzahl von K aufeinanderfolgenden Bitwechseln

Schwer

Sie erhalten ein binäres Array nums und eine Ganzzahl k.

Bei einem k-Bit-Flip wird ein Subarray der Länge k aus Nums ausgewählt und gleichzeitig jede 0 im Subarray in 1 und jede 1 im Subarray in 0 geändert.

Gib die Mindestanzahl von k-Bit-Flips zurück, die erforderlich sind, damit es keine 0 im Array gibt. Wenn dies nicht möglich ist, geben Sie -1 zurück.

Ein Subarray ist ein zusammenhängender Teil eines Arrays.

Beispiel 1:

• Eingabe: nums = [0,1,0], k = 1
• Ausgabe: 2
• Erklärung: Nums[0] umdrehen, dann Nums[2] umdrehen.

Beispiel 2:

• Eingabe: nums = [1,1,0], k = 2
• Ausgabe: -1
• Erklärung: Egal wie wir Subarrays der Größe 2 umdrehen, wir können das Array nicht zu [1,1,1] machen.

Beispiel 3:

• Eingabe: nums = [0,0,0,1,0,1,1,0], k = 3
• Ausgabe: 3
• Erklärung:

  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]

Einschränkungen:

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

Lösung:

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




Kontaktlinks


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt von. Mindestanzahl von K aufeinanderfolgenden Bitwechseln. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!