995.Minimum-Number-of-K-Consecutive-Bit-Flips

995. Minimum Number of K Consecutive Bit Flips

้ข˜็›ฎๅœฐๅ€

https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/

้ข˜็›ฎๆ่ฟฐ

In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of K-bit flips required so that there is no 0 in the array.  If it is not possible, return -1.

Example 1:
Input: A = [0,1,0], K = 1
Output: 2
Explanation: Flip A[0], then flip A[2].

Example 2:
Input: A = [1,1,0], K = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2, we can't make the array become [1,1,1].
Example 3:

Input: A = [0,0,0,1,0,1,1,0], K = 3
Output: 3
Explanation:
Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0]
Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0]
Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]

ไปฃ็ 

Approach 1: Greedy + Events

Flip ^0 = flip

Flip ^1 = ~flip

class Solution {
  public int minKBitFlips(int[] A, int K) {
        int N = A.length;
    int[] hint = new int[N];
    int ans = 0, flip = 0;

    for (int i = 0; i < N; i++) {
      flip ^= hint[i]; // first 0^0 = 0
      if (A[i] == flip) {
        ans++;
        if (i + K > N) {
          return -1;
        }
        flip ^= 1; // 0^1 = 1, 1^1 = 0
        if (i + K < N) {
          hint[i + K] ^= 1;
        }
      }
    }

    return ans;
  }
}

Approach #2

่งฃๆณ•๏ผŒ่ดชๅฟƒ ่ฏๆ˜Ž๏ผš ๅฆ‚ๆžœ็ฌฌไธ€ไธชๆ˜ฏ0๏ผŒ ๅฎƒๅˆซๆ— ้€‰ๆ‹ฉ๏ผŒๅช่ƒฝๅธฆๅŠจๅณ่พน็š„K-1ไธชไธ€่ตท่ฝฌๅฅ‡ๆ•ฐๆฌกใ€‚๏ผˆๅ› ไธบๆฑ‚ๆœ€ๅฐ๏ผŒๆˆ‘ไปฌๅช่ฝฌไธ€ๆฌก๏ผ‰ ๅฆ‚ๆžœ็ฌฌไธ€ไธชๆ˜ฏ1๏ผŒ ๅฎƒๅˆซๆ— ้€‰ๆ‹ฉ๏ผŒๅช่ƒฝๅธฆๅŠจๅณ่พน็š„K-1ไธชไธ€่ตท่ฝฌๅถๆ•ฐๆฌกใ€‚๏ผˆๅ› ไธบๆฑ‚ๆœ€ๅฐ๏ผŒ ๆˆ‘ไปฌ่ฝฌ 0ๆฌก๏ผ‰ ็Žฐๅœจ็ฌฌไธ€ไธชๆžๅฎšไบ†๏ผŒ ไธ‹้ข่งฃๅ†ณ N - 1็š„ๅญ้—ฎ้ข˜ใ€‚

ไฝ†ไธ็ฎกๆ€Žไนˆๆ ท๏ผŒ่ฏทไธ่ฆๅŠจๅ‰้ขๅทฒ็ปๅค„็†ๅฅฝ็š„ใ€‚ไธ‡ไธ€ไฝ ๅŠจไบ†๏ผŒไฝ ่ฟ˜ๅพ—ๅŠจๅ›žๆฅ๏ผŒไธๆŠ˜่…พใ€‚

public int minKBitFlips(int[] A, int K) {
    int count = 0;
    for (int i = 0; i < A.length; i++) {
        if (A[i] == 1) continue;
        if (i + K - 1 < A.length) {
            for (int j = 0; j < K; j++) {
                A[i + j] = 1 - A[i + j];
            }
            count++;
        } else {
            return -1;
        }
    }
    return count;
}

Last updated