Số lần tối thiểu K lần lật bit liên tiếp trong C ++

Giả sử chúng ta có một mảng A. Đây là mảng chỉ chứa các số 0 và 1, ở đây một phép lật K-bit bao gồm việc chọn một mảng con (liền kề) có độ dài K và đảo ngược đồng thời các bit n của mảng con. Chúng ta phải tìm số lần lật K-bit tối thiểu cần thiết để không có số 0 trong mảng. Nếu không có khả năng như vậy, hãy trả về -1.

Vì vậy, nếu đầu vào là [0,0,0,1,0,1,1,0] và K =3, thì đầu ra sẽ là 3, vì chúng ta cần thực hiện các phép toán ba lần, trong lần thử đầu tiên lật A [0] thành A [3], mảng sẽ là [1,1,1,1,0,1,1,0], trong lần chạy thứ hai, lật A [4] thành A [6], mảng sẽ là [1,1,1,1,1,0,0,0] và trong lần di chuyển thứ 3 thay đổi A [5] thành A [7], mảng sẽ là [1,1,1,1,1 , 1,1,1].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

n:=kích thước của A
Xác định di chuyển mảng có kích thước n
bộ đếm:=0
để khởi tạo i:=0, khi i + K <=n, cập nhật (tăng i lên 1), thực hiện -
- nếu tôi> 0, thì -
  - di chuyển [i]:=di chuyển [i] + di chuyển [i - 1]
- nếu không ((move [i] mod 2) + A [i]) mod 2 khác 0, thì -
  - di chuyển [i]:=di chuyển [i] + 1
  - nếu i + K
    - di chuyển [i + K] - =1
  - (tăng bộ đếm lên 1)
cho tôi
- nếu tôi> 0, thì -
  - di chuyển [i]:=di chuyển [i] + di chuyển [i - 1]
- nếu không ((move [i] mod 2) + A [i]) mod 2 khác 0, thì -
  - trả về -1
quầy trả hàng

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Đầu ra

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minKBitFlips(vector<int>& A, int K){
      int n = A.size();
      vector<int> moves(n);
      int i;
      int counter = 0;
      for (i = 0; i + K <= n; i++) {
         if (i > 0)
         moves[i] += moves[i - 1];
         if (!(((moves[i] % 2) + A[i]) % 2)) {
            moves[i] += 1;
            if (i + K < n)
               moves[i + K] -= 1;
            counter++;
         }
      }
      for (; i < n; i++) {
         if (i > 0)
         moves[i] += moves[i - 1];
         if (!(((moves[i] % 2) + A[i]) % 2))
            return -1;
      }
      return counter;
   }
};
main(){
   Solution ob;
   vector<int> v = {0,0,0,1,0,1,1,0};
   cout << (ob.minKBitFlips(v, 3));
}

Đầu vào

{0,0,0,1,0,1,1,0}, 3