This is the seventh day of my participation in the August More text Challenge. For details, see: August More Text Challenge
Leetcode -457- Whether circular arrays have loops
[Blog link]
The way to study 🐔
The nuggets home page
[Topic description]
There is a circular array nums without zeros, and each NUMs [I] represents the number of subscripts that the role at subscript I should move forward or backward:
- if
nums[i]Be positive,forwardmobilenums[i]步 - if
nums[i]Is negative,backwardmobilenums[i]步
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 an array consists of a sequence seq of length k with subscript:
- Following the above movement rules results in repeated subscripts
seq[0] -> seq[1] -> ... -> seq[k - 1] -> seq[0] -> ... - all
nums[seq[j]]Shall notAll areisAll negative k > 1
Return true if nums has a loop; Otherwise, return false **.
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 codeExample 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 codeExample 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 codeTip:
1 <= nums.length <= 5000-1000 <= nums[i] <= 1000nums[i] ! = 0
Advanced: Can you design an algorithm of O(n) time complexity and O(1) extra space complexity?
Related Topics
-
An array of
-
Hash table
-
Double pointer
-
👍 👎 0 121
[Topic link]
Leetcode title link
[making address]
Code link
[思路介绍]
Idea 1: Hash + class depth-first traversal
- Iterating from the current node to repeating the node element at the starting index position represents a loop
- Nodes traversed are stored through a set, which does not exceed the size of the array
- If it is repeated and not satisfied, you can return false directly
- At the same time, judge whether the elements in the ring are all positive/all negative
public boolean circularArrayLoop(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
if (check(nums, i)) {
return true; }}return false;
}
public boolean check(int[] nums, int i) {
int n = nums.length;
// Return false if the starting point can be directly to the end
if (nums[i] % n == 0) {
return false;
}
int cur = nums[i] > 0 ? 1 : -1;
Set<Integer> set = new HashSet<>();
set.add(i);
while (set.size() <= n) {
// Exception
if (nums[i] % n == 0 || cur * nums[i] < 0) {
return false;
}
if (i + nums[i] < 0) {
i = Math.abs((n + i + nums[i]) % n);
} else if (i + nums[i] >= n) {
i = (i + nums[i] - n) % n;
} else {
i = i + nums[i];
}
if (set.contains(i)) {
return true;
}
set.add(i);
}
return false;
}
Copy the code- Time complexity O(n^{2})
- Space complexity O(n)
Idea 2: Optimization of idea 1
- The next index in the coordinate shift can be optimized for judgment
- Math.abs((n + i + nums[i]) % n)
public boolean circularArrayLoop(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
if (check(nums, i)) {
return true; }}return false;
}
public boolean check(int[] nums, int i) {
int n = nums.length;
// Return false if the starting point can be directly to the end
if (nums[i] % n == 0) {
return false;
}
int cur = nums[i] > 0 ? 1 : -1;
Set<Integer> set = new HashSet<>();
set.add(i);
while (set.size() <= n) {
// Exception
if (nums[i] % n == 0 || cur * nums[i] < 0) {
return false;
}
i = Math.abs((n + i + nums[i]) % n);
if (set.contains(i)) {
return true;
}
set.add(i);
}
return false;
}
Copy the code- Time complexity O(n^{2})
- Space complexity O(n)
Idea 3: Further optimization of idea 1
- You can do that without a set
- Because a circular array goes through a point at the end, we iterate through the state of each node as the starting node
- So when judging, we just need to judge whether we can return to the state of the repeated node
- The size can also be determined by using the CNT number pointer
public boolean circularArrayLoop(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
if (check(nums, i)) {
return true; }}return false;
}
public boolean check(int[] nums, int i) {
int n = nums.length;
int cur =i, k = 1;
while (k <= n) {
// Exception: single point cycle | | non-unidirectional movement
if (nums[i] % n == 0 || nums[cur] * nums[i] < 0) {
return false;
}
i = Math.abs((n + i + nums[i]) % n);
if (i == cur ){
return true;
}
k++;
}
return false;
}
Copy the code- Time complexity O(n^{2})
- Space complexity O(1)
Train of thought four: fast and slow pointer
- It’s easy to think of the loop finding method for a two-way linked list
- How fast a pointer
- The proof principle might be understood as
- If there is a ring, the fast and slow Pointers must meet, and the meeting node is the starting node of the ring
- The proof process can refer to Leetcode -141- Circular linked list
- It also needs to determine whether it is one-way
int slow = 0, fast = 0, n = 0;
int[] _nums;
public boolean circularArrayLoop(int[] nums) {
_nums = nums;
n = nums.length;
// There may be more than one ring
for (int i = 0; i < nums.length; i++) {
slow = i;
fast = i;
move();
while(slow ! = fast) { move(); }// Loop the current point
if (nums[slow] % n == 0) {
continue;
}
/ / FeiChanXiang
int temp = slow;
move();
while(temp ! = slow) {if (nums[temp] * nums[slow] < 0) {
break;
}
move();
}
if (temp == slow){
return true; }}return false;
}
public void move(a) {
slow = Math.abs((n + slow + _nums[slow]) % n);
fast = Math.abs((n + fast + _nums[fast]) % n);
fast = Math.abs((n + fast + _nums[fast]) % n);
}
Copy the code- Time complexity O(n^{2})
- Space complexity O(1)
Idea 5: Optimization of idea 4
- The fast and slow pointer can be directly assigned a value of 0 for special loop cases, and no longer traversal
- In this case, the speed pointer formed by traversing all nodes can be guaranteed to be O(n) time complexity
int n = 0;
int[] _nums;
public boolean circularArrayLoop(int[] nums) {
_nums = nums;
n = nums.length;
// There may be more than one ring
for (int i = 0; i < nums.length; i++) {
// The already scanned points can be traversed without repeating
if (nums[i] == 0) {
continue;
}
int slow = i, fast = move(i);
// Fast and slow Pointers move in the same direction
while (nums[slow] * nums[fast] > 0 && nums[slow] * nums[move(fast)] > 0) {
if (slow == fast) {
// Non-self ring
if(slow ! = move(slow)) {return true;
}
// Self loop
else {
break;
}
}
slow = move(slow);
fast = move(move(fast));
}
// If a loop is not formed after a one-way scan, the value 0 can be assigned directly without repeated scanning
int temp = i;
while (nums[temp] * nums[move(temp)] > 0) {
int tmp = temp;
temp = move(temp);
nums[tmp] = 0; }}return false;
}
public int move(int i) {
return Math.abs((n + (i + _nums[i]) % n) % n);
//return ((i + _nums[i]) % n + n) % n;
}
Copy the code- Time complexity O(n)
- Space complexity O(1)
Idea 6: Figure
- This train of thought is the train of thought of three leaf big guy, somewhat difficult to understand
- Define a sufficiently large number, OFFSET, as the OFFSET
- Every time you get to one, you do the +1 operation
- Returns true if a non-loop is detected
public boolean circularArrayLoop(int[] nums) {
int OFFSET = 100010;
int n = nums.length;
for (int i = 0; i < n; i++) {
// We have already traversed the nodes that cannot be looped, so we can not repeat the traversal
if (nums[i] >= OFFSET) continue;
// Represents the current node, the value of the node, and the length of the previous node
int cur = i, tag = OFFSET + i, last = -1;
// Represents the direction in which the node moves
int flag = nums[cur] ;
while (true) {
// Next node
int next = ((cur + nums[cur]) % n + n ) % n;
// The length of the move
last = nums[cur];
// The current node has been traversed
nums[cur] = tag;
// The node moves to the next bit
cur = next;
// Repeat a node -- jump out of the loop
if (cur == i) break;
// Already traversed
if (nums[cur] >= OFFSET) break;
// Determine whether one direction is correct
if (flag * nums[cur] < 0) break;
}
// If the loop is traversed only once, the loop is satisfied
if(last % n ! =0 && nums[cur] == tag) return true;
}
return false;
}
Copy the code- Time complexity O(n)
- Space complexity O(1)