สมมติว่าเรามีจำนวนเต็ม n หนึ่งตัว ข้างในนั้นเราสามารถทำการพลิกหนึ่งบิตเพื่อสร้างลำดับที่ยาวที่สุดของ 1 วินาที สมมติว่าตัวเลขคือ 13 ดังนั้นการแทนค่าเลขฐานสองคือ 1101 หากเราทำการพลิกหนึ่งบิตเป็น 0 ถึง 1 มันจะเป็น 1111 นี่เป็นลำดับที่ยาวที่สุดของ 1 วินาที
เพื่อแก้ปัญหานี้ เราจะอธิบายเกี่ยวกับบิตของตัวเลขที่ระบุ เราจะติดตามความยาวลำดับของ 1 ปัจจุบัน และความยาวของลำดับของ 1 ก่อนหน้า เมื่อพบศูนย์แล้วให้อัปเดตความยาวก่อนหน้า ดังนั้นหากบิตถัดไปคือ 1 ดังนั้นควรตั้งค่าความยาวก่อนหน้าเป็นความยาวปัจจุบัน หากตัวถัดไปเป็น 0 ให้เปลี่ยนค่าก่อนหน้าเป็น 0 อีกครั้ง
ตัวอย่าง
#include<iostream>
using namespace std;
int singleFlipMaxOnes(unsigned number) {
if (~number == 0)
return 8*sizeof(int);
int curr = 0, prev = 0, max_size = 0;
while (number!= 0) {
if ((number & 1) == 1)
curr++;
else if ((number & 1) == 0) {
prev = (number & 2) == 0? 0 : curr;
curr = 0;
}
max_size = max(prev + curr, max_size);
number >>= 1;
}
return max_size+1;
}
int main() {
cout << "Maximum length of the sequence with 1s: " << singleFlipMaxOnes(13);
} ผลลัพธ์
Maximum length of the sequence with 1s: 4
