สมมติว่าเรามีอาร์เรย์ A ซึ่งมีเพียง 0s และ 1s ในที่นี้การพลิก K-bit ประกอบด้วยการเลือกอาร์เรย์ย่อย (ที่อยู่ติดกัน) ที่มีความยาว K และกลับบิต n อาร์เรย์ย่อยพร้อมกัน เราต้องหาจำนวนขั้นต่ำของ K-bit flips ที่ต้องการเพื่อที่จะไม่มี 0 ในอาร์เรย์ หากไม่มีความเป็นไปได้ดังกล่าว ให้คืนค่า -1
ดังนั้นหากอินพุตเป็น [0,0,0,1,0,1,1,0] และ K =3 เอาต์พุตจะเป็น 3 เนื่องจากเราต้องดำเนินการสามครั้งในการลองครั้งแรก พลิก A[0] เป็น A[3] อาร์เรย์จะเป็น [1,1,1,1,0,1,1,1,0] ในการเรียกใช้ครั้งที่สองพลิก A[4] ถึง A[6] อาร์เรย์ จะเป็น [1,1,1,1,1,0,0,0] และในการย้ายครั้งที่ 3 เปลี่ยน A[5] เป็น A[7] อาร์เรย์จะเป็น [1,1,1,1,1,1 ,1,1,1].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
n :=ขนาดของ A
-
กำหนดการย้ายอาร์เรย์ขนาด n
-
เคาน์เตอร์ :=0
-
สำหรับการเริ่มต้น i :=0 เมื่อ i + K <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ -
-
ถ้า i> 0 แล้ว −
-
การเคลื่อนไหว[i] :=การเคลื่อนไหว[i] + การเคลื่อนไหว[i - 1]
-
-
ถ้าไม่ใช่ ((ย้าย[i] mod 2) + A[i]) mod 2 ไม่เป็นศูนย์ ดังนั้น −
-
การเคลื่อนไหว[i] :=การเคลื่อนไหว[i] + 1
-
ถ้า i + K
-
การเคลื่อนไหว[i + K] - =1
-
-
(เพิ่มตัวนับทีละ 1)
-
-
-
สำหรับ i
-
ถ้า i> 0 แล้ว −
-
การเคลื่อนไหว[i] :=การเคลื่อนไหว[i] + การเคลื่อนไหว[i - 1]
-
-
ถ้าไม่ใช่ ((ย้าย[i] mod 2) + A[i]) mod 2 ไม่เป็นศูนย์ ดังนั้น −
-
กลับ -1
-
-
-
เคาน์เตอร์คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ผลลัพธ์
#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));
} อินพุต
{0,0,0,1,0,1,1,0}, 3 ผลลัพธ์
3
