โปรแกรมสร้างตัวเลขน้อยที่สุดที่ไม่มีเลขติดกันซ้ำใน Python

สมมติว่าเรามีสตริง s ที่มี 4 ตัวอักษรที่เป็นไปได้ "1", "2", "3" และ "?" เราสามารถวาง "1", "2" หรือ "3" แทน "?" ได้ เราต้องหาตัวเลขน้อยที่สุดที่เป็นไปได้ ที่ไม่มีสองหลักติดกันเหมือนกัน

เช่น ถ้าอินพุตคือ s = "2??3?" ผลลัพธ์จะเป็น 21231

ขั้นตอนการแก้ปัญหา

1. i := 0, s := รายการจาก s
2. ถ้า ขนาดของ s < 2 และ s[i] == "?" คืนค่า "1"
3. ในขณะที่ i < ขนาดของ s:
   • ถ้า s[i] == "?":
     • ถ้า i == 0: s[i] := "1" ถ้า s[i+1] != "1" มิฉะนั้น "2"
     • มิฉะนั้นถ้า i > 0 และ i <= ขนาดของ s - 2:
       • ถ้า s[i-1] == "1": s[i] := "3" ถ้า s[i+1] == "2" มิฉะนั้น "2"
       • มิฉะนั้นถ้า s[i-1] == "2": s[i] := "3" ถ้า s[i+1] == "1" มิฉะนั้น "1"
       • มิฉะนั้นถ้า s[i-1] == "3": s[i] := "2" ถ้า s[i+1] == "1" มิฉะนั้น "1"
     • มิฉะนั้น: s[i] := "1" ถ้า s[i-1] != "1" มิฉะนั้น "2"
   • i := i + 1
4. รวมสมาชิก s เป็นสตริงและคืนค่า

ตัวอย่างการใช้งาน

def solve(s):
    i = 0
    s = list(s)
    if len(s) < 2:
        if s[i] == "?":
            return "1"
    while i < len(s):
        if s[i] == "?":
            if i == 0:
                s[i] = "1" if s[i + 1] != "1" else "2"
            elif i > 0 and i <= len(s) - 2:
                if s[i - 1] == "1":
                    if s[i + 1] == "2":
                        s[i] = "3"
                    else:
                        s[i] = "2"
                elif s[i - 1] == "2":
                    if s[i + 1] == "1":
                        s[i] = "3"
                    else:
                        s[i] = "1"
                elif s[i - 1] == "3":
                    if s[i + 1] == "1":
                        s[i] = "2"
                    else:
                        s[i] = "1"
            else:
                s[i] = "1" if s[i - 1] != "1" else "2"
        i += 1
    return "".join(s)

s = "2??3?"
print(solve(s))

อินพุต

"2??3?"

เอาต์พุต

21231