Chương trình nhóm các số 1 với số lượng hoán đổi tối thiểu trong một chuỗi nhất định bằng Python

Giả sử chúng ta được cung cấp một chuỗi nhị phân input_str chứa 0s và 1s. Nhiệm vụ của chúng ta là nhóm các số 0 và 1 bằng cách hoán đổi các số 1 trong chuỗi đã cho. Chúng ta phải thực hiện một số thao tác hoán đổi tối thiểu và chúng ta phải trả về giá trị đó. Một điều cần lưu ý, chúng ta chỉ có thể hoán đổi các giá trị liền kề.

Vì vậy, nếu đầu vào là input_str =10110101, thì đầu ra sẽ là 4

Việc hoán đổi sẽ như sau -

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

Tổng số lần hoán đổi:4.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• one:=một danh sách mới chứa các vị trí trong input_str nơi chứa các vị trí 1
• mid:=giá trị sàn của (kích thước 1/2)
• res:=0
• đối với tôi trong phạm vi từ 0 đến kích thước của một, hãy thực hiện
  • res:=res + | one [mid] - one [i] | - | giữa - i |
• nếu res <0, thì
  • trả về 0
• nếu không,
  • trả lại res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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'))

Đầu vào

'10110101'

Đầu ra

4