Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में रेंज मॉड्यूल (Range Module)


मान लीजिए हम एक रेंज मॉड्यूल (Range Module) चाहते हैं। यह एक मॉड्यूल है जो संख्याओं की रेंज को ट्रैक करता है। हमारा कार्य निम्न इंटरफेस को कुशल तरीके से डिजाइन और कार्यान्वित करना है।

  • addRange(left, right)। यह अर्ध-खुले अंतराल [left, right) को ट्रैक करेगा, उस अंतराल में हर वास्तविक संख्या को ट्रैक करेगा। अब, एक अंतराल जोड़ना जो वर्तमान में ट्रैक की गई संख्याओं के साथ आंशिक रूप से ओवरलैप करता है, उस अंतराल में किसी भी संख्या को जोड़ देगा जो पहले से ट्रैक नहीं की गई है।
  • queryRange(left, right)। यह true वापस करेगा जब अंतराल [left, right) में हर वास्तविक संख्या वर्तमान में ट्रैक की जा रही हो।
  • removeRange(left, right), यह अंतराल [left, right) में वर्तमान में ट्रैक की जा रही हर वास्तविक संख्या को ट्रैक करना बंद कर देगा।

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

  • एक मैप m परिभाषित करें
  • एक फंक्शन addRange() परिभाषित करें, यह left, right लेगा,
  • removeRange(left, right)
  • m[left] := right
  • it := वह स्थान जहां left, m में मौजूद है
  • यदि यह m के पहले तत्व के बराबर नहीं है और it के पिछले का दूसरा मान, left के समान है, तो -
    • (it को 1 से घटाएं)
    • it का दूसरा मान := right
    • m से left हटाएं
  • यदि यह m के अंतिम तत्व के पिछले के बराबर नहीं है और it के अगले का पहला मान, right के समान है, तो -
    • it का दूसरा मान := next(it) का दूसरा मान
    • m से next(it) हटाएं
  • एक फंक्शन queryRange() परिभाषित करें, यह left, right लेगा,
  • it := m के उस सबपार्ट का स्थान जहां सभी मान left से छोटे हैं
  • यदि m खाली है या यह m के पहले तत्व के समान है, तो -
    • false वापस करें
  • (it को 1 से घटाएं)
  • वापस करें true जब it का दूसरा मान >= right
  • एक फंक्शन removeRange() परिभाषित करें, यह left, right लेगा,
  • यदि m खाली है, तो -
    • वापस करें
  • it := m के उस सबपार्ट का स्थान जहां सभी मान left से बड़े हैं
  • यदि यह m के पहले तत्व के बराबर नहीं है, तो -
    • (it को 1 से घटाएं)
  • एक ऐरे v परिभाषित करें
  • जब (it, m के अंतिम तत्व के बराबर नहीं है और it का पहला मान < right), करें -
    • यदि it का पहला मान < left और it का दूसरा मान > left, तो -
      • temp := it का दूसरा मान
      • it का दूसरा मान := left
      • यदि temp > right, तो: m[right] := temp
    • अन्यथा जब it का पहला मान >= left, तो -
      • v के अंत में it का पहला मान डालें
      • यदि it का दूसरा मान > right, तो -
        • m[right] := it का दूसरा मान
    • (it को 1 से बढ़ाएं)
  • i := 0 से प्रारंभ करें, जब i < v का आकार, i बढ़ाते हुए, करें -
    • m से v[i] हटाएं

बेहतर समझ के लिए निम्न कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h> using namespace std; class RangeModule { public:    map <int, int> m;    RangeModule() {    }    void addRange(int left, int right) {       removeRange(left, right);       m[left] = right;       map <int, int> :: iterator it = m.find(left);       if(it != m.begin() && prev(it)->second == left){          it--;          it->second = right;          m.erase(left);       }       if(it != prev(m.end()) && next(it)->first == right){          it->second = next(it)->second;          m.erase(next(it));       }    }    bool queryRange(int left, int right) {       map <int, int> :: iterator it = m.upper_bound(left);       if(m.empty() || it == m.begin())return false;       it--;       return it->second >= right;    }    void removeRange(int left, int right) {       if(m.empty())return;       map <int, int> :: iterator it = m.lower_bound(left);       if(it != m.begin())it--;       vector <int> v;       while(it != m.end() && it->first < right){          if(it->first < left && it->second > left){             int temp = it->second;             it->second = left;             if(temp > right){                m[right] = temp;             }          }else if(it->first >= left){             v.push_back(it->first);             if(it->second > right){                m[right] = it->second;             }          }          it++;       }       for(int i = 0; i < v.size(); i++){          m.erase(v[i]);       }    } }; main(){    RangeModule ob;    ob.addRange(10,20);    ob.removeRange(14,16);    cout << (ob.queryRange(10,14)) << endl;    cout << (ob.queryRange(13,15)) << endl;    cout << (ob.queryRange(16,17)); }

इनपुट

Add range (10,20) Remove Range (14,16) Check ranges (10,14), (13,15), (16,17)

आउटपुट

1 0 1

  1. C++ में ट्री में एक पंक्ति जोड़ें C++ में ट्री में एक पंक्ति जोड़ें

    मान लीजिए हमारे पास एक बाइनरी ट्री है, हमारे पास मान v और गहराई d भी है, हमें दिए गए गहराई d पर मान v वाले नोड्स की एक पंक्ति जोड़नी है। रूट नोड गहराई 1 पर है। हमें इस ऑपरेशन को करने के लिए निम्न नियम का पालन करना होगा: चूंकि हमें गहराई d पता है, गहराई d-1 पर प्रत्येक वैध ट्री नोड N के लिए, हमें मा

  1. C++ में बाइनरी ट्री की सीमा C++ में बाइनरी ट्री की सीमा

    मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें इसके सीमा के मानों को रूट से शुरू करके वामावर्त दिशा में ढूंढना है। यहां सीमा में बायां सीमा, पत्ते, और दायां सीमा क्रम में बिना डुप्लिकेट नोड्स के शामिल हैं। बायां सीमा रूट से बाएं-सबसे नोड तक का पथ है। दायां सीमा रूट से दाएं-सबसे नोड तक का पथ है। जब रू

  1. C++ में अधिकतम बाइनरी ट्री निर्माण C++ में अधिकतम बाइनरी ट्री निर्माण

    मान लीजिए हमारे पास एक पूर्णांक सरणी है जिसके सभी तत्व अद्वितीय हैं। एक अधिकतम बाइनरी ट्री निम्न नियमों से बनता है: रूट सरणी का अधिकतम तत्व होता है। बायाँ सबट्री अधिकतम तत्व के बाएँ भाग से बने सबसरणी का अधिकतम ट्री होता है। दायाँ सबट्री अधिकतम तत्व के दाएँ भाग से बने सबसरणी का अधिकतम ट्री होता है।