. K 연속 비트 뒤집기의 최소 수

995. 최소 K 연속 비트 플립 수

하드

이진 배열 nums와 정수 k가 주어졌습니다.

k 비트 플립은 숫자에서 길이가 k인 하위 배열을 선택하고 동시에 하위 배열의 모든 0을 1로, 하위 배열의 모든 1을 0으로 변경하는 것입니다.

배열에 0이 없도록 필요한 최소 k 비트 플립 수를 반환합니다. 불가능할 경우 -1을 반환합니다.

하위 배열은 배열의 인접 부분입니다.

예 1:

• 입력: nums = [0,1,0], k = 1
• 출력: 2
• 설명: 숫자[0]을 뒤집은 다음 숫자[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 <= nums.length <= 10⁵
• 1 <= k <= nums.length

해결책:

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




연락처 링크


링크드인
깃허브



          

            
  

            
        
위 내용은 . K 연속 비트 뒤집기의 최소 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!