โปรแกรมตรวจสอบว่ามี Forward Path อยู่ในรายการ Circular cyclic หรือไม่ใน Python

สมมติว่าเรามีรายการวงกลมที่เรียกว่า nums ดังนั้นองค์ประกอบแรกและองค์ประกอบสุดท้ายคือเพื่อนบ้าน ดังนั้นเริ่มต้นจากดัชนีใดๆ ที่บอกว่า i เราสามารถย้าย nums[i] จำนวนก้าวไปข้างหน้าได้หาก nums[i] เป็นค่าบวก หรือถอยหลังหากเป็นค่าลบ เราต้องตรวจสอบว่ามีวัฏจักรใดที่มีความยาวมากกว่า 1 รอบ โดยที่เส้นทางเดินไปข้างหน้าหรือถอยหลังเท่านั้น

ดังนั้น หากอินพุตเป็น nums =[-1, 2, -1, 1, 2] เอาต์พุตจะเป็น True เพราะมีเส้นทางไปข้างหน้า [1 -> 3 -> 4 -> 1]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

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

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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