ตรวจสอบเส้นทางตัดกันเองใน C++ (Self Crossing)

ภาพรวมปัญหา

เริ่มที่ (0,0) เดิน: x[0] 北, x[1] 西, x[2] 南, x[3] 東, ... (หมุนทวนเข็มนาฬิกา) ตรวจสอบว่าเส้นทางตัดตัวเองหรือไม่ O(1) space

ตัวอย่าง

x = [3,4,2,5] → true (ตัดกัน)

วิธีแก้ปัญหา: รูปแบบ 3 กรณี

เส้นทางตัดกันได้ 3 แบบ:
1. วงจร 4 ขั้น: x[i] ≥ x[i-2] และ x[i-1] ≤ x[i-3]
2. วงจร 5 ขั้น: x[i] + x[i-4] ≥ x[i-2] และ x[i-1] = x[i-3]
3. วงจร 6 ขั้น: x[i] + x[i-4] ≥ x[i-2] และ x[i-1] + x[i-5] ≥ x[i-3] และ x[i-1] ≤ x[i-3]

โค้ดด้านล่างใช้วิธี compact: เพิ่ม 0 4 ตัวหน้า, แล้วเช็คเงื่อนไข 2 ขั้นตอน

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isSelfCrossing(vector<int>& x) {
        x.insert(x.begin(), 4, 0); // pad 4 zeros at front
        int n = x.size(), i = 4;
        for (; i < n && x[i] > x[i-2]; i++); // spiral out
        if (i == n) return false;
        if (x[i] >= x[i-2] - x[i-4]) x[i-1] -= x[i-3]; // transition
        for (i++; i < n && x[i] < x[i-2]; i++); // spiral in
        return i != n;
    }
};

int main() {
    Solution ob;
    vector<int> v = {3,4,2,5};
    cout << (ob.isSelfCrossing(v));
}

ผลลัพธ์

1 (true)

การวิเคราะห์ความซับซ้อน

• เวลา: O(n)
• พื้นที่: O(1) เพิ่มเติม (modify input array)