Giả sử chúng ta có một mảng x gồm n số. Chúng tôi bắt đầu tại điểm (0,0) và di chuyển x [0] đơn vị về hướng bắc, sau đó x [1] đơn vị về hướng tây, x [2] đơn vị về hướng nam, x [3] đơn vị về hướng đông hướng và như vậy. Nói cách khác, sau mỗi lần di chuyển, hướng của chúng ta thay đổi ngược chiều kim đồng hồ. Chúng tôi phải nghĩ ra một thuật toán một lần với O (1) khoảng trống thừa để xác định xem đường đi của chúng tôi có tự cắt hay không.
Vì vậy, nếu mảng giống như - [3,4,2,5]
Câu trả lời sẽ đúng.
Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -
-
chèn 0 vào chỉ mục 4 của x
-
n:=kích thước của x, i:=4
-
vì không khởi tạo bất kỳ thứ gì khi i
x [i - 2], hãy tăng i lên 1 do - -
Không làm gì
-
-
nếu tôi giống với n, thì trả về false
-
nếu x [i]> =x [i - 2] - x [i - 4] thì
-
x [i - 1] =x [i - 1] - x [i - 3]
-
-
để tăng i lên 1, khi i
-
Không làm gì
-
-
trả về true khi tôi không giống với n
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isSelfCrossing(vector<int>& x) {
x.insert(x.begin(), 4, 0);
int n = x.size();
int i = 4;
for(; i < n && x[i] > x[ i - 2];i++);
if(i == n) return false;
if (x[i] >= x[i - 2] - x[i - 4]){
x[i - 1] -= x[i - 3];
}
for (i++; i < n && x[i] < x[i - 2]; i++);
return i != n;
}
};
main(){
Solution ob;
vector<int> v = {3,4,2,5};
cout << (ob.isSelfCrossing(v));
} Đầu vào
{3,4,2,5} Đầu ra
1