ধরুন আমাদের কাছে পূর্ণসংখ্যার একটি অ্যারে গ্রহাণু রয়েছে যা একটি সারিতে গ্রহাণুকে উপস্থাপন করে। এখন প্রতিটি গ্রহাণুর জন্য, পরম মান তার আকারের প্রতিনিধিত্ব করে, এবং চিহ্নটি তার দিক নির্দেশ করে যা যথাক্রমে ডান এবং বামের জন্য ইতিবাচক বা ঋণাত্মক হতে পারে। প্রতিটি গ্রহাণু একই গতিতে চলে।
সমস্ত সংঘর্ষের পরে আমাদের গ্রহাণুগুলির অবস্থা খুঁজে বের করতে হবে। দুটি গ্রহাণু মিলিত হলে ছোটটি বিস্ফোরিত হবে। উভয়ই একই আকারের হলে উভয়ই বিস্ফোরিত হবে। একই দিকে চলমান দুটি গ্রহাণু কখনই মিলিত হবে না।
সুতরাং ইনপুট যদি [5, 10, -5] এর মত হয়, তাহলে আউটপুট হবে [5, 10]। এখানে 10 এবং -5 10 তে সংঘর্ষ হয়, তারপর 5 এবং 10 কখনই সংঘর্ষ হয় না।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি অ্যারে ret করুন, n :=অ্যারের আকার
-
0 থেকে n – 1
রেঞ্জের i জন্য-
যদি ret খালি হয় বা ret-এর শেষ উপাদান ধনাত্মক হয় এবং arr[i] ঋণাত্মক হয়, তাহলে
-
ret এ arr[i] ঢোকান, i 1 দ্বারা বাড়ান
-
-
অন্যথায়
-
x :=ret এর শেষ উপাদান, ret থেকে শেষ উপাদান মুছে দিন
-
absX :=|x|, absY :=|arr[i]|
-
যদি absX =absY, তাহলে i বাড়ান 1
-
অন্যথায়
-
যদি absX> absY, তাহলে ret-এ x ঢোকান, i বাড়ান 1
-
-
-
-
রিটার্ন রিটার্ন
উদাহরণ (C++)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#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:
bool isNeg(int x){
return x < 0;
}
vector<int> asteroidCollision(vector<int>& arr) {
vector <int> ret;
int n = arr.size();
for(int i = 0; i< n; ){
if(ret.empty() || !(!isNeg(ret[ret.size() - 1]) && isNeg(arr[i]))){
ret.push_back(arr[i]);
i++;
} else {
int x = ret[ret.size() - 1];
ret.pop_back();
int absX = abs(x);
int absY = abs(arr[i]);
if(absX == absY){
i++;
} else {
if(absX > absY){
ret.push_back(x);
i++;
}
}
}
}
return ret;
}
};
main(){
vector<int> v = {5, 10, -4};
Solution ob;
print_vector(ob.asteroidCollision(v));
} ইনপুট
[5,10,-4]
আউটপুট
[5, 10, ]
