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