मान लीजिए हमारे पास n संख्याओं की एक सरणी x है। हम बिंदु (0,0) से शुरू करते हैं और x[0] इकाई उत्तर दिशा में चलते हैं, फिर x[1] इकाई पश्चिम दिशा में, x[2] इकाई दक्षिण दिशा में, x[3] इकाई पूर्व दिशा में और इसी तरह। दूसरे शब्दों में, प्रत्येक चाल के बाद हमारी दिशा वामावर्त बदलती है। हमें O(1) अतिरिक्त स्थान के साथ एक-पास एल्गोरिदम तैयार करना है यह निर्धारित करने के लिए कि हमारा पथ स्वयं को पार करता है या नहीं।
तो यदि सरणी जैसी है - [3,4,2,5]
उत्तर true होगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
x के इंडेक्स 4 पर 0 डालें
n := x का आकार, i := 4
कुछ भी आरंभ न करने के लिए जब i < n और x[i] > x[i - 2], i को 1 से बढ़ाएं करें -
कुछ न करें
यदि i, n के समान है, तो, false लौटाएं
यदि x[i] >= x[i - 2] - x[i - 4], तो,
x[i - 1] = x[i - 1] - x[i - 3]
i को 1 से बढ़ाएं, जब i < n और x[i] < x[i - 2], 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
