Question
Formatted question description: https://leetcode.ca/all/335.html
335 Self Crossing
You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north,
then x[1] metres to the west, x[2] metres to the south, x[3] metres to the east and so on.
In other words, after each move your direction changes counter-clockwise.
Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.
Example 1:
┌───┐
│ │
└───┼──>
│
Input: [2,1,1,2]
Output: true
Example 2:
┌──────┐
│ │
│
│
└────────────>
Input: [1,2,3,4]
Output: false
Example 3:
┌───┐
│ │
└───┼>
Input: [1,1,1,1]
Output: true
Algorithm
In fact, there are only three cases of intersection:
x(1)
┌───┐
x(2)│ │x(0)
└───┼──>
x(3)│
The first type is the case where the fourth side and the first side intersect. The conditions that need to be met are that the first side is greater than or equal to the third side, and the fourth side is greater than or equal to the second side. The same applies to the case where the fifth side intersects the second side, the sixth side intersects the third side, and so on, and so on.
x(1)
┌──────┐
│ │x(0)
x(2)│ ^
│ │x(4)
└──────│
x(3)
The second type is the case where the fifth side and the first side overlap and intersect. The conditions that need to be met are that the second side and the fourth side are equal, and the fifth side is greater than or equal to the third side and the first side. The difference is also applicable to the case where the sixth edge and the second edge overlap and intersect, and so on, and so on…
x(1)
┌──────┐
│ │x(0)
x(2)│ <│────│
│ x(5)│x(4)
└───────────│
x(3)
The third category is the intersection of the sixth side and the first side. The conditions that need to be met are that the fourth side is greater than or equal to the second side, the third side is greater than or equal to the fifth side, and the fifth side is greater than or equal to The difference between the third side and the first side, the sixth side is greater than or equal to the difference between the fourth side and the second side, the same applies to the intersection of the seventh side and the second side, and so on.
Code
Java
public class Self_Crossing {
class Solution {
public boolean isSelfCrossing(int[] x) {
for (int i = 3; i < x.length; ++i) {
if (x[i] >= x[i - 2] && x[i - 3] >= x[i - 1]) {
return true;
}
if (i >= 4 && x[i-1] == x[i-3] && x[i] >= x[i-2] - x[i-4]) {
return true;
}
if (i >= 5 && x[i-2] >= x[i-4] && x[i-3] >= x[i-1] && x[i-1] >= x[i-3] - x[i-5] && x[i] >= x[i-2] - x[i-4]) {
return true;
}
}
return false;
}
}
}