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