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

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

ดังนั้น หากอินพุตเป็น s ="11100011" เอาต์พุตจะเป็น 3 เพราะหากเราพลิกบิตที่ตำแหน่ง 1, 4 และ 7 มันจะเป็น "10101010" ทั้งหมดก็จะสลับกัน

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

• เปลี่ยน :=0

• even_1 :=0, even_0 :=0

• odd_1 :=0, odd_0 :=0

• สำหรับฉันในช่วง 0 ถึงขนาด s - 1 ทำ

  • ถ้าฉันเท่ากันแล้ว

    • ถ้า s[i] เหมือนกับ '1' แล้ว

      • even_1 :=คู่ _1 + 1

    • มิฉะนั้น

      • even_0 :=คู่ _0 + 1

  • มิฉะนั้น

    • ถ้า s[i] เหมือนกับ '1' แล้ว

      • odd_1 :=odd_1 + 1

    • มิฉะนั้น

      • คี่_0 :=คี่_0 + 1

• if (even_1+odd_0)> (even_0+odd_1) แล้ว

  • เปลี่ยน :=คู่ _0 + คี่_1

• มิฉะนั้น

  • เปลี่ยน :=คู่ _1 + คี่_0

• ผลตอบแทนการเปลี่ยนแปลง

ตัวอย่าง (Python)

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

def solve(s):
   change = 0
   even_1 = 0
   even_0 = 0
   odd_1 = 0
   odd_0 = 0
   for i in range(len(s)):
      if(i%2 == 0):
         if(s[i]=='1'):
            even_1 +=1
         else:
            even_0 +=1
      else:
         if(s[i] == '1'):
            odd_1 +=1
         else:
            odd_0 +=1
   if((even_1+odd_0)>(even_0+odd_1)):
      change = even_0 + odd_1
   else:
      change = even_1 + odd_0
   return change

s = "11100011"
print(solve(s))

อินพุต

"11100011"

ผลลัพธ์

3