Chương trình kiểm tra xem có bất kỳ đường dẫn chuyển tiếp nào trong danh sách tuần hoàn tròn hay không trong Python

Giả sử chúng ta có một danh sách hình tròn được gọi là nums. Vì vậy, yếu tố đầu tiên và yếu tố cuối cùng là hàng xóm của nhau. Vì vậy, bắt đầu từ bất kỳ chỉ mục nào nói rằng i, chúng ta có thể di chuyển nums [i] số bước về phía trước nếu nums [i] là một giá trị dương, ngược lại nếu nó là một giá trị âm. Chúng ta phải kiểm tra xem có chu kỳ nào có độ dài lớn hơn một chu trình để đường dẫn chỉ đi về phía trước hoặc chỉ đi ngược lại hay không.

Vì vậy, nếu đầu vào giống như nums =[-1, 2, -1, 1, 2], thì đầu ra sẽ là True, vì có một đường dẫn phía trước [1 -> 3 -> 4 -> 1]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của nums
• nếu n giống 0, thì
  • trả về Sai
• saw:=một mảng có kích thước n và điền bằng 0
• cập nhật nums bằng cách lấy x mod n cho mỗi phần tử x trong nums
• iter:=0
• đối với tôi trong phạm vi từ 0 đến n - 1, thực hiện
  • nếu nums [i] giống 0, thì
    • chuyển sang lần lặp tiếp theo
  • iter:=iter + 1
  • pos:=True
  • neg:=True
  • curr:=i
  • Thực hiện lặp đi lặp lại những điều sau đây, hãy thực hiện
    • nếu nums [curr] và saw [curr] giống với iter, thì
      • trả về True
    • nếu see [curr] khác 0, thì
      • ra khỏi vòng lặp
    • nếu nums [curr]> 0, thì
      • neg:=False
    • nếu không,
      • pos:=False
    • nếu cả hai đều là neg và pos, thì
      • ra khỏi vòng lặp
    • saw [curr]:=iter
    • curr:=(curr + nums [curr] + n) mod n
    • nếu nums [curr] giống 0, thì
      • ra khỏi vòng lặp
• trả về Sai

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

True