n개의 숫자로 구성된 배열 x가 있다고 가정합니다. 점 (0,0)에서 시작하여 x[0] 단위를 북쪽 방향으로 이동한 다음 x[1] 단위를 서쪽 방향으로, x[2] 단위를 남쪽 방향으로, x[3] 단위를 동쪽으로 이동합니다. 방향 등이 있다. 다시 말해서, 각각의 이동 후에 우리의 방향은 시계 반대 방향으로 바뀝니다. 경로가 자체 교차하는지 여부를 결정하기 위해 O(1) 추가 공간이 있는 원패스 알고리즘을 고안해야 합니다.
따라서 배열이 − [3,4,2,5]
와 같은 경우 
대답은 사실일 것입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
x의 인덱스 4에 0 삽입
-
n :=x의 크기, i :=4
-
i
x[i - 2]일 때 아무것도 초기화하지 않으려면 i를 1만큼 증가 do - -
아무것도 하지 않음
-
-
i가 n과 같으면 false를 반환합니다.
-
x[i]>=x[i - 2] - x[i - 4]이면,
-
x[i - 1] =x[i - 1] - x[i - 3]
-
-
i를 1만큼 증가시키려면 i
-
아무것도 하지 않음
-
-
i가 n과 같지 않으면 true를 반환합니다.
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#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