Chương trình tìm chuỗi nhị phân lớn nhất sau biến đổi trong Python

Giả sử có chuỗi nhị phân. Có thể áp dụng vô số lần:

• Thay "00" bằng "10"
• Thay "10" bằng "01"

Tìm chuỗi nhị phân lớn nhất (theo giá trị số) sau các phép biến đổi.

Ví dụ: s = "001100", đầu ra = "111011".

Giải pháp

Quan sát: phép biến đổi cho phép di chuyển các '0' sang phải và gom các '1' sang trái. Kết quả tối ưu: tất cả '1' ở đầu, rồi một '0', rồi các '1' còn lại.

• length := len(s), zeros := s.count('0')
• Nếu zeros < 2: trả về s
• s := s.lstrip('1') (bỏ '1' đầu)
• leading_ones := length - len(s) + zeros - 1
• trailing_ones := length - leading_ones - 1
• Trả về '1' * leading_ones + '0' + '1' * trailing_ones

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

def solve(s):
    length = len(s)
    zeros = s.count('0')
    if zeros < 2:
        return s
    s = s.lstrip('1')
    leading_ones = length - len(s)
    leading_ones += zeros - 1
    trailing_ones = length - leading_ones - 1
    answer_left = '1' * leading_ones
    answer_right = '1' * trailing_ones
    return ''.join([answer_left, '0', answer_right])

s = "001100"
print(solve(s))

Đầu vào

"001100"

Đầu ra

111011