Giả sử chúng ta có một chuỗi nhị phân. Chúng ta có thể áp dụng từng thao tác sau vào bất kỳ số lần nào -
-
Nếu số chứa chuỗi con "00", chúng ta có thể thay thế nó bằng "10".
-
Nếu số chứa chuỗi con "10", chúng ta có thể thay thế nó bằng "01".
Sau đó, chúng tôi phải tìm chuỗi nhị phân tối đa (dựa trên giá trị số của nó) mà chúng tôi có thể nhận được số lượng phép toán sau.
Vì vậy, nếu đầu vào là s ="001100", thì đầu ra sẽ là 111011, bởi vì chúng ta có thể chuyển dạng như (00) 1100 -> 101 (10) 0 -> 1010 (10) -> 10 (10) 01 -> 100 (10) 1 -> 1 (00) 011 -> 111011.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- length:=kích thước của s
- số không:=số chữ số 0 tính bằng s
- nếu các số không <2, thì
- trả lại s
- s:=loại bỏ tất cả '1 từ bên trái của s
- lead_ones:=chiều dài - kích thước của s
- lead_ones:=lead_ones + zeros - 1
- trailing_ones:=length - lead_ones - 1
- answer_left:=lead_ones số 1 giây
- answer_right:=trailing_ones số 1 giây
- answer_left nối 0 nối answer_right và trả về
Ví dụ
Hãy cùng chúng tôi xem cách 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