สมมติว่าเราได้รับสตริงไบนารี input_str ที่มี 0s และ 1s งานของเราคือการจัดกลุ่ม 0s และ 1 โดยการแลกเปลี่ยน 1s ในสตริงที่กำหนด เราต้องดำเนินการแลกเปลี่ยนตามจำนวนขั้นต่ำ และเราต้องคืนค่านั้น สิ่งหนึ่งที่ต้องจำไว้คือ เราสามารถสลับค่าที่อยู่ติดกันเท่านั้น
ดังนั้น หากอินพุตเป็นเหมือน input_str =10110101 ผลลัพธ์จะเป็น 4
การแลกเปลี่ยนจะเป็นดังนี้ -
10110101->01110101->01111001->01111010->01111100
จำนวนสวอปทั้งหมด:4.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- one :=รายการใหม่ที่มีตำแหน่งใน input_str ซึ่งเป็นที่ตั้งของ 1s
- กลาง :=มูลค่าพื้นของ (ขนาดหนึ่ง / 2)
- res :=0
- สำหรับ i ในช่วง 0 ถึงขนาดหนึ่ง ทำ
- res :=res + |one[mid] - one[i]| - |กลาง - i|
- ถ้า res <0 แล้ว
- คืน 0
- มิฉะนั้น
- ผลตอบแทน
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
