สมมติว่าเรามีสตริงไบนารี s ตอนนี้ให้เราพิจารณาการดำเนินการที่เราเลือกบิตและพลิกค่าจาก 0 เป็น 1 หรือกลับกัน เราต้องหาจำนวนการดำเนินการขั้นต่ำที่จำเป็นเพื่อให้ได้สตริงที่ไม่มีบิตต่อเนื่องกันสามบิต
ดังนั้น หากอินพุตเป็น s ="10011100" ผลลัพธ์จะเป็น 1 เนื่องจากเราสามารถพลิก 1 ถึง 0 บิตที่ดัชนี 4 เพื่อทำให้สตริง "10010100" ไม่มีบิตเหมือนกันสามบิตต่อเนื่องกัน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- l :=0, จำนวน :=0
- ในขณะที่ l <ขนาดของ s ทำ
- r :=ล
- ในขณะที่ r
- r :=r + 1
- นับ :=นับ + ชั้นของ ((r - l) / 3)
- l :=r
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(s): l = 0 count = 0 while l < len(s): r = l while r < len(s) and s[r] == s[l]: r += 1 count += (r - l) // 3 l = r return count s = "10011100" print(solve(s))
อินพุต
"10011100"
ผลลัพธ์
1
