โปรแกรมจัดกลุ่ม 1 ให้อยู่ติดกันด้วยการสลับน้อยที่สุดใน Python

สมมติว่าเราได้รับสตริงไบนารี input_str ที่ประกอบด้วย 0 และ 1 งานคือจัดกลุ่ม 0 และ 1 ให้อยู่ติดกันโดยการสลับ 1 ในสตริงที่กำหนด ต้องทำการสลับน้อยที่สุด และคืนค่าจำนวนครั้งที่สลับ สิ่งสำคัญคือ สลับได้เฉพาะค่าที่อยู่ติดกันเท่านั้น

เช่น ถ้าอินพุตคือ input_str = 10110101 ผลลัพธ์จะเป็น 4

การสลับจะเป็นดังนี้:

10110101 -> 01110101 -> 01111001 -> 01111010 -> 01111100

จำนวนครั้งที่สลับทั้งหมด: 4

ขั้นตอนการแก้ปัญหา

1. one := รายการใหม่ที่เก็บตำแหน่งใน input_str ที่มีค่า 1
2. mid := floor(ขนาดของ one / 2)
3. res := 0
4. สำหรับ i ในช่วง 0 ถึง ขนาดของ one:
   • res := res + |one[mid] - one[i]| - |mid - i|
5. ถ้า res < 0 คืนค่า 0 มิฉะนั้นคืนค่า res

ตัวอย่างการใช้งาน

def solve(input_string):
    one = [i for i in range(len(input_string)) if input_string[i] == "1"]
    mid = len(one) // 2
    res = 0
    for i in range(len(one)):
        res += abs(one[mid] - one[i]) - abs(mid - i)
    return 0 if res < 0 else res

print(solve('10110101'))

อินพุต

'10110101'

เอาต์พุต

4