C++ এ স্বয়ং ক্রসিং

ধরুন আমাদের 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 −

  দ্বারা সূচনা না করার জন্য

  • কিছুই করবেন না

• যদি আমি 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