循環循環リストにフォワードパスがあるか、Pythonにないかをチェックするプログラム

numsという循環リストがあるとします。したがって、最初と最後の要素はネイバーです。したがって、任意のインデックス（i）から開始して、nums [i]が正の値の場合は、nums [i]のステップ数を前方に移動できます。それ以外の場合は、負の値の場合は後方に移動できます。パスが前方にのみ進むか、後方にのみ進むように、長さが1より大きいサイクルがあるかどうかを確認する必要があります。

したがって、入力がnums =[-1、2、-1、1、2]のようである場合、順方向パス[1-> 3-> 4-> 1]

これを解決するには、次の手順に従います-

• n：=numsのサイズ
• nが0と同じ場合、
  • Falseを返す
• saw：=サイズnの配列で、0で埋める
• numsの各要素xに対してxmodnを取得してnumsを更新します
• iter：=0
• 0からn-1の範囲のiの場合、do
  • nums [i]が0と同じ場合、
    • 次の反復に進む
  • iter：=iter + 1
  • pos：=True
  • neg：=True
  • curr：=i
  • 次のことを繰り返し実行します。
    • nums[curr]とseen[curr]がiterと同じ場合、
      • Trueを返す
    • sawed [curr]がゼロ以外の場合、
      • ループから抜け出す
    • nums [curr]> 0の場合、
      • neg：=False
    • それ以外の場合、
      • pos：=False
    • negとposの両方がfalseの場合、
      • ループから抜け出す
    • sawed [curr]：=iter
    • curr：=（curr + nums [curr] + n）mod n
    • nums [curr]が0と同じ場合、
      • ループから抜け出す
• 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