ধরুন আমাদের 0s এবং 1s এর একটি অ্যারে রয়েছে, আমাদের অ্যারেটিকে 3টি অ-খালি অংশে ভাগ করতে হবে যাতে এই সমস্ত অংশ একই বাইনারি মান উপস্থাপন করে। যদি তা সম্ভব হয়, i+1
-
A[0], A[1], ..., A[i] হল প্রথম অংশ;
-
A[i+1], A[i+2], ..., A[j-1] হল দ্বিতীয় অংশ, এবং
-
A[j], A[j+1], ..., A[A.length - 1] হল তৃতীয় অংশ।
তিনটি অংশেরই সমান বাইনারি মান রয়েছে। যদি তা সম্ভব না হয়, [-1, -1] ফেরত দিন।
সুতরাং, ইনপুট যদি [0,1,0,1,1] এর মত হয়, তাহলে আউটপুট হবে [0,4]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন getIdx() সংজ্ঞায়িত করুন, এটি একটি অ্যারে, বাম, ডান,
নেবে -
যখন (বাম <ডান এবং একটি [বাম] 0 এর মতো), −
করুন-
(বামে 1 দ্বারা বাড়ান)
-
-
ডানদিকে <(int)a.size(), −
করুন-
যদি একটি [বাম] একটি [ডান] এর সমান না হয়, তাহলে, ফিরুন -1
-
(1 দ্বারা বাম বাড়ান), (1 দ্বারা ডানে বাড়ান)
-
-
বাম দিকে ফিরুন - 1
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
সাইজ 2 এর একটি অ্যারে রেট সংজ্ঞায়িত করুন -1
দিয়ে এটি পূরণ করুন -
num :=0, n :=A
এর আকার -
আরম্ভ করার জন্য i :=0, যখন i
-
num :=num + 1 যখন (A[i] 1 এর সমান), অন্যথায় 0
-
-
যদি num mod 3 0 এর সমান না হয়, তাহলে −
-
রিটার্ন রিটার্ন
-
-
যদি সংখ্যাটি 0 এর মতো হয়, তাহলে −
-
{ 0, 2 }
ফেরত দিন
-
-
অনুরোধ :=সংখ্যা / 3
-
idx :=n - 1
-
আরম্ভ করার জন্য temp :=0, যখন idx>=0 এবং temp
-
temp :=temp + 1 যখন (A[idx] 1 এর মতো), অন্যথায় 0
-
-
(আইডিএক্স 1 দ্বারা বাড়ান)
-
ফার্স্টএন্ড :=getIdx(A, 0, idx)
-
যদি প্রথম শেষ হয় <0, তারপর −
-
রিটার্ন রিটার্ন
-
-
সেকেন্ডএন্ড :=getIdx(A, firstEnd + 1, idx)
-
সেকেন্ডএন্ড <0 হলে −
-
রিটার্ন রিটার্ন
-
-
ফিরুন { firstEnd, secondend + 1 }
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: vector<int> threeEqualParts(vector<int>& A){ vector<int> ret(2, -1); int num = 0; int n = A.size(); for (int i = 0; i < n; i++) { num += (A[i] == 1); } if (num % 3 != 0) return ret; if (num == 0) { return { 0, 2 }; } int req = num / 3; int idx = n - 1; for (int temp = 0; idx >= 0 && temp < req; idx--) { temp += A[idx] == 1; } idx++; int firstEnd = getIdx(A, 0, idx); if (firstEnd < 0) return ret; int secondEnd = getIdx(A, firstEnd + 1, idx); if (secondEnd < 0) return ret; return { firstEnd, secondEnd + 1 }; } int getIdx(vector<int>& a, int left, int right){ while (left < right && a[left] == 0) left++; while (right < (int)a.size()) { if (a[left] != a[right]) return -1; left++; right++; } return left - 1; } }; main(){ Solution ob; vector<int> v = {0,1,0,1,1}; print_vector(ob.threeEqualParts(v)); }
ইনপুট
{0,1,0,1,1}
আউটপুট
[1, 4, ]