สมมติว่าเรามีสตริงไบนารี เราสามารถใช้การดำเนินการต่อไปนี้กี่ครั้งก็ได้ -
-
หากตัวเลขมีสตริงย่อย "00" เราสามารถแทนที่ด้วย "10"
-
หากตัวเลขมีสตริงย่อย "10" เราสามารถแทนที่ด้วย "01" ได้
จากนั้นเราต้องค้นหาสตริงไบนารีสูงสุด (ตามค่าตัวเลข) ที่เราจะได้รับหลังจากดำเนินการตามจำนวนครั้ง
ดังนั้น หากอินพุตเป็น s ="001100" ผลลัพธ์จะเป็น 111011 เพราะเราสามารถถ่ายโอนได้เช่น (00)1100 -> 101(10)0 -> 1010(10) -> 10(10)01 -> 100(10)1 -> 1(00)011 -> 111011
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ความยาว :=ขนาด s
- ศูนย์ :=จำนวน 0 วินาทีในหน่วย s
- ถ้าเป็นศูนย์ <2 แล้ว
- คืนสินค้า
- s :=ลบ '1's ทั้งหมดจากด้านซ้ายของ s
- leading_ones :=length - size of s
- leading_ones :=lead_ones + ศูนย์ - 1
- trailing_ones :=length - lead_ones - 1
- answer_left :=lead_ones จำนวน 1 วินาที
- answer_right :=trailing_ones จำนวน 1 วินาที
- answer_left concatenate 0 concatenate answer_right and return
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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)) อินพุต
"001100"
ผลลัพธ์
111011
