C++ में क्षुद्रग्रह टकराव

मान लीजिए हमारे पास पूर्णांकों की एक सरणी asteroids है जो एक पंक्ति में क्षुद्रग्रहों का प्रतिनिधित्व करती है। अब प्रत्येक क्षुद्रग्रह के लिए, निरपेक्ष मान उसका आकार दर्शाता है, और चिह्न उसकी दिशा दर्शाता है जो दाएं के लिए धनात्मक और बाएं के लिए ऋणात्मक हो सकती है। प्रत्येक क्षुद्रग्रह समान गति से चलता है।

हमें सभी टकरावों के बाद क्षुद्रग्रहों की स्थिति ढूंढनी है। जब दो क्षुद्रग्रह मिलते हैं, तो छोटा वाला फट जाएगा। यदि दोनों समान आकार के हैं, तो दोनों फट जाएंगे। एक ही दिशा में चलने वाले दो क्षुद्रग्रह कभी नहीं मिलेंगे।

उदाहरण के लिए, यदि इनपुट [5, 10, -5] जैसा है, तो आउटपुट [5, 10] होगा। यहां 10 और -5 10 में टकराते हैं, फिर 5 और 10 कभी नहीं टकराएंगे।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

• ret नामक एक सरणी बनाएं, n := arr का आकार
• i को 0 से n - 1 तक लूप करें
  • यदि ret खाली है या ret का अंतिम तत्व धनात्मक है और arr[i] ऋणात्मक है, तो
    • arr[i] को ret में डालें, i को 1 से बढ़ाएं
  • अन्यथा
    • x := ret का अंतिम तत्व, ret से अंतिम तत्व हटाएं
    • absX := |x|, absY := |arr[i]|
    • यदि absX = absY, तो i को 1 से बढ़ाएं
    • अन्यथा
      • यदि , तो x को ret में डालें, i को 1 से बढ़ाएं
• ret लौटाएं

उदाहरण (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, ]