C ++中的循环数组循环

假设我们有一个正整数和负整数的圆形数组。如果索引处的数字k为正数，则向前移动k步。否则，如果它是负数(-k)，则向后移动k步。由于数组是圆形的，因此我们可以假定最后一个元素的下一个元素是第一个元素，而第一个元素的前一个元素是最后一个元素。我们必须检查是否存在以数字为单位的循环（或循环）。一个循环必须在相同的索引处开始和结束，并且循环的长度>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

• 对于i，范围为0至n – 1

• temp：=慢速下一个

• 慢的下一个：= 0

• 慢：=温度

• 慢=慢的下一个

• 快速：=快速的下一个

• 如果慢=快速，则

• 如果慢=慢的下一个，则从循环中出来

• 返回真

• 如果nums [i] = 0，则继续下一次迭代；

• 慢=我，快=我;

• 而nums [slow] * nums [fast]> 0和nums [next of fast] * nums [slow]> 0

• x：= nums [i]

• 慢：=我

• 而nums [slow] * x> 0

• 返回假

让我们看下面的实现以更好地理解-

示例

#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