โปรแกรมหาจำนวนพลิกขั้นต่ำที่จำเป็นในการมีค่าสลับกันใน Python

สมมติว่าเรามีสตริงไบนารี s สมมติว่าเราสามารถนำหน้าของ s มาไว้ข้างหลังได้ จากนั้นให้หาจำนวนอักขระขั้นต่ำที่ต้องพลิกเพื่อไม่ให้มีอักขระต่อเนื่องกันที่มีค่าเท่ากัน

ดังนั้น หากอินพุตเป็น s ="10010101111" ผลลัพธ์จะเป็น 2 เนื่องจากเราสามารถนำหน้า "10" ได้ จากนั้นเลื่อนไปทางด้านหลังเพื่อให้สตริงเป็น "01010111110" จากนั้นจึงพลิกบิตที่ 3 และ 5 จากขวาเป็น 0 ("01010101010")

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ตอบ :=ไซส์ S

• N :=ไซส์ S

• s :=0

• สำหรับฉันอยู่ในช่วง 0 ถึง 2 * N ทำ

  • s :=s + จำนวนเต็มของ (S[i mod N] XOR (i AND 1))

  • ถ้า i>=N - 1 แล้ว

    • ans :=ขั้นต่ำของ ans, s และ N - s

    • s :=s - จำนวนเต็มของ (S[(i -(N - 1)) mod N]) XOR ((i - (N - 1)) และ 1)

• กลับมาอีกครั้ง

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

class Solution:
   def solve(self, S):
      ans = N = len(S)
      s = 0
      for i in range(2 * N):
         s += int(S[i % N]) ^ (i & 1)
         if i >= N - 1:
            ans = min(ans, s, N - s)
            s -= int(S[(i - (N - 1)) % N]) ^ ((i - (N - 1)) & 1)
      return ans
ob = Solution()
s = "10010101111"
print(ob.solve(s))

อินพุต

"10010101111"

ผลลัพธ์

2