สมมติว่าเรามีอาร์เรย์ x ของ n ตัวเลข เราเริ่มต้นที่จุด (0,0) และเคลื่อน x[0] หน่วยไปทางทิศเหนือ จากนั้น x[1] หน่วยไปทางทิศตะวันตก x[2] หน่วยไปทางทิศใต้ , x[3] หน่วยไปทางทิศตะวันออก ทิศทางและอื่น ๆ กล่าวอีกนัยหนึ่ง หลังจากที่แต่ละการเคลื่อนไหว ทิศทางของเราจะเปลี่ยนทวนเข็มนาฬิกา เราต้องสร้างอัลกอริธึมหนึ่งรอบโดยมีพื้นที่พิเศษ O(1) เพื่อพิจารณาว่าเส้นทางของเราตัดผ่านหรือไม่
ดังนั้นหากอาร์เรย์เป็นแบบ − [3,4,2,5]
คำตอบจะเป็นจริง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
แทรก 0 ที่ดัชนี 4 ของ x
-
n :=ขนาดของ x, ผม :=4
-
สำหรับการไม่เริ่มต้นอะไรเลยเมื่อ i
x[i - 2] ให้เพิ่ม i ขึ้น 1 ทำ − -
ไม่ทำอะไรเลย
-
-
ถ้าฉันเหมือนกับ n ให้คืนค่าเท็จ
-
ถ้า x[i]>=x[i - 2] - x[i - 4] แล้ว
-
x[i - 1] =x[i - 1] - x[i - 3]
-
-
เพื่อเพิ่ม i ขึ้น 1 เมื่อฉัน
-
ไม่ทำอะไรเลย
-
-
คืนค่า จริง เมื่อฉันไม่เหมือนกับ 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));
} อินพุต
{3,4,2,5} เอาท์พุต
1
