“This is the 15th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Topic:

There is a circular array nums without zero, and each nums[I] represents the number of subscripts that the character at subscript I should move forward or backward:

  • If the nums [I] is positive, forward (subscript incremental direction) mobile | nums [I] | step

  • If nums [I] is negative, backward (subscript decreasing direction) mobile | nums [I] | step

Because the array is circular, it can be assumed that a step forward from the last element will reach the first element, and a step back from the first element will reach the last element.

The loop in the array is identified by the subscript sequence seq of length K:

  • Following the above movement rules results in a sequence of repeated subscripts seq[0] -> SEq [1] ->… -> seq[k – 1] -> seq[0] -> …

  • All NUMs [seq[j]] should be either positive or negative

  • k > 1

Return true if there are loops in nums; Otherwise, return false.

Example 1: Input: nums = [2,-1,1,2,2] Output: true Description: There is a loop, press the subscript 0 -> 2 -> 3 -> 0. The loop length is 3. Example 2: Input: nums = [-1,2] Output: false Description: Press the subscript 1 -> 1 -> 1... The motion of phi cannot form a cycle because the length of the cycle is one. By definition, the length of the loop must be greater than 1. Example 3: input: nums = [2, 1, 1, 2, 2] output: false interpretation: according to the subscript 1 - > 2 - > 1 - >... The motion of cannot form a loop because NUMs [1] is positive and NUMs [2] is negative. All NUMs [seq[j]] should be either positive or negative.Copy the code

Note:

  • 1 <= nums.length <= 5000
  • -1000 <= nums[i] <= 1000
  • nums[i] ! = 0

Answer:

Today’s topic meaning is difficult to understand, do not understand the topic of the friends can see this section of the meaning of the analysis.

First, understand what a “ring array” is. A ring array is an array that is logically end to end, where the last element and the first element are logically adjacent (it is still a normal array in physical storage).

So what does it mean to have a loop in a circular array? That is, in a circular array, the elements stored at each position represent the number of steps forward/backward that should be taken at the current position. If you go all the way around an array of rings and come back to the same place, there is a loop in the array.

For example, in the circular array [2, -1, 1, 2, 2], there is a loop, and the conditions for the loop are specified: all nums[seq[j]] should be either completely positive or completely negative, i.e., they can only go in one direction; K > 1, that is, the size of the ring is greater than 1.

I have done the topic of “judging whether there is a ring in the linked list”, and these two questions have the same idea. The common idea is the fast and slow pointer. In the linked list problem, the fast pointer takes 2 steps each time, and the slow pointer takes 1 step each time. When the fast and slow hands meet, it indicates the existence of a ring.

During each loop, you must ensure that all the numbers you experience are the same.

So, at each position that the fast pointer goes through, check to see if it’s the same symbol as the starting number.

When the fast and slow hands meet, check that the ring size is not 1.

So, if you take one more step after finding the location of the meeting point, determine whether it is you.

  • source

JavaScript implementation:

var circularArrayLoop = function(nums) { const n = nums.length; for (let i = 0; i < n; i++) { if (nums[i] === 0) { continue; } let slow = i, fast = next(nums, i); While (nums[slow] * nums[fast] > 0 && nums[slow] * nums[next(nums, fast)] > 0) { if (slow === fast) { if (slow ! == next(nums, slow)) { return true; } else { break; } } slow = next(nums, slow); fast = next(nums, next(nums, fast)); } let add = i; while (nums[add] * nums[next(nums, add)] > 0) { const tmp = add; add = next(nums, add); nums[tmp] = 0; } } return false; } const next = (nums, cur) => { const n = nums.length; return ((cur + nums[cur]) % n + n) % n; // Make sure the return value is in [0,n]}Copy the code

I’m Nuggets Anthony, output exposure input, technical insight into life, goodbye ~