Vòng lặp mảng tròn trong C ++

Giả sử chúng ta có một số mảng tròn gồm các giá trị nguyên dương và âm. Nếu một số k tại một chỉ số là một số dương, thì hãy tiến lên k bước. Ngược lại, nếu nó âm (-k), hãy lùi lại k bước. Vì mảng là hình tròn, chúng ta có thể giả sử rằng phần tử tiếp theo của phần tử cuối cùng là phần tử đầu tiên và phần tử trước của phần tử đầu tiên là phần tử cuối cùng. Chúng ta phải kiểm tra xem có một vòng lặp (hoặc một chu kỳ) trong nums hay không. Một chu kỳ phải bắt đầu và kết thúc ở cùng một chỉ mục và độ dài của chu kỳ> 1. Vì vậy, nếu đầu vào là [2, -1,1,2,2], thì đầu ra sẽ đúng, vì có một chu kỳ từ chỉ mục 0 -> 2 -> 3 -> 0 của độ dài 3.

Để 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 <2, thì trả về false
đối với tôi trong phạm vi từ 0 đến n - 1, nums [i]:=nums [i] mod n
cho tôi trong phạm vi từ 0 đến n - 1
- nếu nums [i] =0, thì hãy tiếp tục lặp lại tiếp theo;
- chậm =i, nhanh =i;
- trong khi nums [chậm] * nums [nhanh]> 0 và nums [tiếp theo của nhanh] * nums [chậm]> 0
  - chậm =tiếp theo của chậm
  - fast:=next of the next of fast
  - nếu chậm =nhanh thì
    - nếu chậm =tiếp theo của chậm, thì ra khỏi vòng lặp
    - trả về true
- x:=nums [i]
- chậm:=i
- trong khi nums [chậm] * x> 0
  - temp:=tiếp theo của chậm
  - tiếp theo của chậm:=0
  - chậm:=temp
trả về false

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

Ví dụ

#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));
}

Đầu vào

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

Vòng lặp mảng tròn trong C ++

Ví dụ

Đầu vào

Đầu ra