Cho mảng x độ dài n. Bắt đầu từ (0,0), di chuyển: x[0] Bắc, x[1] Tây, x[2] Nam, x[3] Đông, ... (xoay ngược chiều kim đồng hồ). Xác định đường đi có tự cắt nhau hay không. Yêu cầu: 1 lần duyệt, O(1) không gian.
Ví dụ
x = [3,4,2,5] → true (đường cắt nhau).
Quan sát quan trọng
Chỉ có 3 trường hợp tự cắt:
- Case 1 (vòng thứ 4 cắt vòng thứ 1):
x[i] ≥ x[i-2] && x[i-1] ≤ x[i-3] - Case 2 (vòng thứ 5 gặp vòng thứ 1):
i ≥ 4 && x[i-1] == x[i-3] && x[i] + x[i-4] ≥ x[i-2] - Case 3 (vòng thứ 6 cắt vòng thứ 1):
i ≥ 5 && x[i-2] ≥ x[i-4] && x[i] ≥ x[i-2] - x[i-4] && x[i-1] ≥ x[i-3] - x[i-5] && x[i-1] ≤ x[i-3]
Code mẫu dùng cách tiếp cận khác: chèn 4 số 0 vào đầu, sau đó tìm điểm chuyển từ "mở rộng" sang "thu hẹp".
Cài đặt C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isSelfCrossing(vector<int>& x) {
x.insert(x.begin(), 4, 0); // chèn 4 số 0 vào đầu
int n = x.size(), i = 4;
// Giai đoạn mở rộng: x[i] > x[i-2]
for (; i < n && x[i] > x[i-2]; i++);
if (i == n) return false;
// Giai đoạn thu hẹp: kiểm tra điều kiện chuyển tiếp
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;
}
};
int main() {
Solution ob;
vector<int> v = {3, 4, 2, 5};
cout << ob.isSelfCrossing(v);
return 0;
}
Độ phức tạp
- Thời gian:
O(n)— 1 lần duyệt. - Không gian:
O(1)— sửa mảng đầu vào.
Input / Output
Input: {3,4,2,5}
Output: 1 (true)