C++での循環配列ループ

正と負の整数値の循環配列numsがあるとします。インデックスの数値kが正の数の場合、kステップ進みます。それ以外の場合、負の値（-k）の場合は、kステップ後方に移動します。配列は円形であるため、最後の要素の次の要素が最初の要素であり、最初の要素の前の要素が最後の要素であると見なすことができます。 numsにループ（またはサイクル）があるかどうかを確認する必要があります。サイクルは同じインデックスで開始および終了する必要があり、サイクルの長さは1より大きい必要があります。したがって、入力が[2、-1,1,2,2]の場合、インデックスからのサイクルがあるため、出力はtrueになります。 0-> 2->3->0の長さ3。

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

• n：=numsのサイズ

  
  

• n <2の場合、falseを返します

  
  

• 0からn-1の範囲のiの場合、nums [i]：=nums [i] mod n

• 0からn–1の範囲のiの場合

  • nums [i] =0の場合、次の反復に進みます。

  • 遅い=i、速い=i;

  • 一方、nums [slow] * nums[fast]>0およびnums[nextof fast] * nums [slow]> 0

    • 遅い=遅いの次

    • fast：=next of the next of fast

    • 遅い=速い場合、

      • 遅い=遅いの次の場合、ループから出てきます

      • trueを返す

  • x：=nums [i]

  • 遅い：=i

  • while nums [slow] * x> 0

    • temp：=次の遅い

    • 次の遅い：=0

    • 遅い：=temp

• falseを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int next(vector<int>& nums, int i){
      int n = nums.size();
      return (n+nums[i]+i)%n;
   }
   bool circularArrayLoop(vector<int>& nums) {
      int n = nums.size();
      if(n < 2) return false;
      for(int i = 0; i < n; i++)nums[i] %= n;
      for(int i = 0; i < n; i++){
         if(nums[i] == 0) continue;
         int slow = i;
         int fast = i;
         while(nums[slow] * nums[fast] > 0 && nums[next(nums, fast)] * nums[slow] > 0){
            slow = next(nums, slow);
            fast = next(nums, next(nums, fast));
            if(slow == fast){
               if(slow == next(nums, slow))
               break;
               return true;
            }
         }
         int x = nums[i];
         slow = i;
         while(nums[slow] * x > 0){
            int temp = next(nums, slow);
            nums[slow] = 0;
            slow = temp;
         }
      }
      return false;
   }
};
main(){
   vector<int> v = {2,-1,1,2,2};
   Solution ob;
   cout << (ob.circularArrayLoop(v));
}

入力

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

出力

1