. Nombre minimum de K retournements de bits consécutifs

995. Nombre minimum de K retournements de bits consécutifs

Dur

Vous recevez un tableau binaire nums et un entier k.

Un retournement de k bits consiste à choisir un sous-tableau de longueur k à partir de nombres et à changer simultanément chaque 0 du sous-tableau en 1 et chaque 1 du sous-tableau en 0.

Renvoie le nombre minimum de retournements de k bits requis pour qu'il n'y ait pas de 0 dans le tableau. Si ce n'est pas possible, retournez -1.

Un sous-tableau est une partie contiguë d'un tableau.

Exemple 1 :

• Entrée : nums = [0,1,0], k = 1
• Sortie : 2
• Explication : Retournez les nombres[0], puis retournez les nombres[2].

Exemple 2 :

• Entrée : nums = [1,1,0], k = 2
• Sortie : -1
• Explication : Peu importe la façon dont nous retournons des sous-tableaux de taille 2, nous ne pouvons pas faire en sorte que le tableau devienne [1,1,1].

Exemple 3 :

• Entrée : nums = [0,0,0,1,0,1,1,0], k = 3
• Sortie : 3
• Explication :

  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]

Contraintes :

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

Solution :

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




Liens de contact


LinkedIn
GitHub



          

            
  

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!