โปรแกรมตรวจสอบว่ามีเส้นทางไปข้างหน้าในรายการวนรอบแบบวงกลมหรือไม่ใน Python

สมมติว่าเรามีรายการวงกลมชื่อ nums ดังนั้นสมาชิกแรกและสุดท้ายจึงเป็นเพื่อนบกัน เริ่มจากดัชนีใดๆ ว่า i เราสามารถเคลื่อนที่ไปข้างหน้า nums[i] ขั้น หาก nums[i] เป็นค่าบวก หรือถอยหลังหากเป็นค่าลบ เราต้องตรวจสอบว่ามีรูปทรงวงจร (cycle) ที่ความยาวมากกว่าหนึ่ง ซึ่งเส้นทางไปเฉพาะข้างหน้าหรือเฉพาะถอยหลังเท่านั้น

เช่น ถ้าอินพุตคือ nums = [-1, 2, -1, 1, 2] ผลลัพธ์จะเป็น True เพราะมีเส้นทางไปข้างหน้า [1 -> 3 -> 4 -> 1]

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

1. n := ขนาดของ nums
2. ถ้า n == 0 คืนค่า False
3. seen := อาร์เรย์ขนาด n เติม 0
4. อัปเดต nums โดยเอา x mod n สำหรับแต่ละสมาชิก x
5. iter := 0
6. สำหรับ i ในช่วง 0 ถึง n-1:
   • ถ้า nums[i] == 0 ข้ามรอบนี้
   • iter := iter + 1
   • pos := True, neg := True, curr := i
   • ทำซ้ำ:
     • ถ้า nums[curr] และ seen[curr] == iter คืนค่า True
     • ถ้า seen[curr] != 0 ออกจากลูป
     • ถ้า nums[curr] > 0 ให้ neg := False มิฉะนั้น pos := False
     • ถ้า neg และ pos ทั้งคู่เป็น False ออกจากลูป
     • seen[curr] := iter
     • curr := (curr + nums[curr] + n) % n
     • ถ้า nums[curr] == 0 ออกจากลูป
7. คืนค่า False

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

def solve(nums):
    n = len(nums)
    if n == 0:
        return False
    seen = [0] * n
    nums = [x % n for x in nums]
    iter = 0
    for i in range(n):
        if nums[i] == 0:
            continue
        iter += 1
        pos = True
        neg = True
        curr = i
        while True:
            if nums[curr] and seen[curr] == iter:
                return True
            if seen[curr]:
                break
            if nums[curr] > 0:
                neg = False
            else:
                pos = False
            if not neg and not pos:
                break
            seen[curr] = iter
            curr = (curr + nums[curr] + n) % n
            if nums[curr] == 0:
                break
    return False

nums = [-1, 2, -1, 1, 2]
print(solve(nums))

อินพุต

[-1, 2, -1, 1, 2]

เอาต์พุต

True