मान लीजिए कि हमारे पास 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 से बढ़ाएँ - -
कुछ न करें
-
-
अगर मैं n के समान हूं, तो झूठी वापसी करें
-
अगर x[i]>=x[i - 2] - x[i - 4], तो,
-
x[i - 1] =x[i - 1] - x[i - 3]
-
-
i को 1 से बढ़ाने के लिए, जब i
-
कुछ न करें
-
-
जब मैं 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