This is the seventh day of my participation in the August More text Challenge. For details, see:August is more challenging

Topic describes

This is 457 on LeetCode. Is there a loop in a circular array? The difficulty is medium.

Tag: “graph”, “simulation”

There is a circular array numsnumsnums without 000, and each nums[I]nums[I]nums[I]nums[I] indicates the number of subscripts that the role at subscript iii should move forward or backward:

  • If nums[I] NUMs [I]nums[I]nums[I] is positive, move nums[I]nums[I]nums[I] forward
  • If nums[I]nums[I]nums[I]nums[I] is negative, move nums[I]nums[I]nums[I] backwards

Since the array is circular, you can assume that a step forward from the last element will lead to the first element, and a step backward from the first element will lead to the last element.

The loop in the array is composed by the sequence seqseqseq of length KKK:

  • Following the above movement rules results in repeated subscriptsseq[0] -> seq[1] -> ... -> seq[k - 1] -> seq[0] -> ...
  • Nums [seq[j]]nums[seq[J]]nums[seq[J]

  • k > 1 k > 1

Return trueTruetrue if there are loops in numsnumsnums; Otherwise, falseFalseFalse is returned.

Example 1:

Input: nums = [2,-1,1,2,2] Output: true Description: a loop exists, press the subscript 0 -> 2 -> 3 -> 0. The length of the cycle is 3.Copy the code

Example 2:

Input: nums = [-1,2] Output: false Description: Press the subscript 1 -> 1 -> 1... The movement of PI cannot form a cycle because the cycle has length one. By definition, the length of the loop must be greater than 1.Copy the code

Example 3:

Input: nums = [2, 1, 1, 2, 2] output: false interpretation: according to the subscript 1 - > 2 - > 1 - >... The movement 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

Tip:

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

Advanced: Can you design an algorithm of O(n) time complexity and O(1) extra space complexity?

simulation

We can check for each subscript iii, returning True if a “loop” is found at any subscript iii, False otherwise.

The only detail we need to pay attention to is that when we deal with the subscript curcurcur, we calculate the next jump point next=cur+nums[cur]next =cur+nums[cur]next =cur+nums[cur]next =cur+nums[cur]next =cur+nums[cur]

  1. If nextNextNext is negative: Add n∗⌈next/n⌉n * \left \lceil next/n \right \rceiln∗⌈next/n⌉ on the basis of nextnextNext, and map it back to a positive value;

  2. If nextNextNext is positive: Lengthen the nextnextNext module NNN, ensuring that the bounds are not crossed.

Next = ((cur + nums[cur]) % n + n) % n.

Inside the check, when any of the following conditions occurs, the check can be finished (let KKK be the number of subscripts scanned during the recording process) :

  1. If k>1k >1k >1 finds the same subscript as the starting point during the check, it indicates that there is a “loop” that meets the condition, and returns True;

  2. If the number of scanning KKK exceeds the array length NNN, then according to the “dovnest principle”, there must be several repeated processing, at the same time, condition 1 does not meet, so further processing will not reach the same index as the starting point, return False;

  3. False if not all positive or negative numbers are found during processing.

Code:

class Solution {
    int n;
    int[] nums;
    public boolean circularArrayLoop(int[] _nums) {
        nums = _nums;
        n = nums.length;
        for (int i = 0; i < n; i++) {
            if (check(i)) return true;
        }
        return false;
    }
    boolean check(int start) {
        int cur = start;
        boolean flag = nums[start] > 0;
        int k = 1;
        while (true) {
            if (k > n) return false;
            int next = ((cur + nums[cur]) % n + n ) % n;
            if (flag && nums[next] < 0) return false;
            if(! flag && nums[next] >0) return false;
            if (next == start) return k > 1; cur = next; k++; }}}Copy the code
  • Time complexity: O(n2)O(n^2)O(n2)
  • Space complexity: O(1)O(1)O(1)

Graph traversal tag (using the new array tag)

This is a complementary approach, more as a transition between “solution 1” and “solution 3”, and it is recommended to study solution 3 after fully understanding this solution.

From Solution One, we see that we double check a lot of duplicate paths.

If there is a loopless path a− B − C − DA – B-C – DA − B − C − D from location AAA to location DDD, according to solution 1, we will check whether there is a loop in path AAA, and then check whether there is a loop in path BBB, CCC and DDD.

In fact, since there is only one exit for each point (the next location to which a location can jump is uniquely determined), we can use a VIS array to record that those subscripts have been checked, thus avoiding the same path being checked twice.

At the same time, we can expandvisThe array function enables it to be used not only to determine whether a location has been checked, but also to record the round in which a location has been checked. Specifically, we make
v i s [ i ] = i d x vis[i] = idx On behalf of the position
i i In the first
i d x idx The wheel is marked.

If vis[next]vis[next] VIS [next]vis[next]vis[next] is not 000, You can tell whether the position is marked in this round by comparing vis[next] VIS [next] VIS [next] with the current round number.

Code:

class Solution {   
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        // Mark each subscript with a VIS array
        Vis [I] = idx if the position with subscript I is marked in round IDx
        int[] vis = new int[n];
        for (int start = 0, idx = 1; start < n; start++, idx++) {
            if(vis[start] ! =0) continue;
            int cur = start;
            boolean flag = nums[cur] > 0;
            while (true) {
                int next = ((cur + nums[cur]) % n + n) % n;
                if (next == cur) break;
                if(vis[next] ! =0) {
                    // If the next point is already marked, and is not marked in the epicycle, then all subsequent paths must be marked, and there is no ring, jump out
                    if(vis[next] ! = idx)break;
                    // If the next point is already marked, and was originally marked, then the ring has been found
                    else return true;
                }
                if (flag && nums[next] < 0) break;
                if(! flag && nums[next] >0) break; vis[next] = idx; cur = next; }}return false; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

Graph traversal tag (using the original array tag)

According to the meaning of the question, we regard each index as a point, and the current point and the next point to which the current point can reach are regarded as an edge.

Thus, the problem is transformed into the classical “graph theory ring seeking” problem, and at the same time, because the degree of each point is fixed as
1 1 , and stipulate that the “loop” must be “in the same direction” to be legal, so if we find a reverse in the process of traversing, we stop checking.

In addition, in order to achieve the space of O(1)O(1)O(1), we need to mark the original array, we set a large enough number OFFSET, for the loop search initiated by the subscript iii, we mark the scanned number as OFFSET + I. If the loop is not found after scanning the loop search initiated by III, the “loop” is found, and True is output.

Code:

class Solution {
    int OFFSET = 100010;
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] >= OFFSET) continue;
            int cur = i, tag = OFFSET + i, last = -1;
            boolean flag = nums[cur] > 0;
            while (true) {
                int next = ((cur + nums[cur]) % n + n ) % n;
                last = nums[cur];
                nums[cur] = tag;
                cur = next;
                if (cur == i) break;
                if (nums[cur] >= OFFSET) break;
                if (flag && nums[cur] < 0) break;
                if(! flag && nums[cur] >0) break;
            }
            if(last % n ! =0 && nums[cur] == tag) return true;
        }
        return false; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

The last

This is article No.457 in our “Brush through LeetCode” series, which began on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some with locks, and we will first brush through all the questions without locks.

In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.

In order to facilitate the students to debug and submit the code on the computer, I set up a related warehouse: github.com/SharingSour… .

In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.