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

C++ में राइट इंटरवल ढूंढना


मान लीजिए हमारे पास इंटरवल्स का एक ऐरे है, प्रत्येक इंटरवल i के लिए, जांचें कि क्या कोई इंटरवल j मौजूद है जिसका स्टार्ट पॉइंट इंटरवल i के एंडपॉइंट से बड़ा या बराबर है, जिसे कहा जा सकता है कि j, i के "राइट" पर है। किसी भी इंटरवल i के लिए, हमें मिनिमम इंटरवल j का इंडेक्स स्टोर करना है, जो दर्शाता है कि इंटरवल j में इंटरवल i के लिए "राइट" रिलेशनशिप बनाने के लिए मिनिमम स्टार्ट पॉइंट है। जब इंटरवल j मौजूद नहीं है, तो इंटरवल i के लिए -1 स्टोर करें। और अंत में, हमें प्रत्येक इंटरवल के स्टोर्ड वैल्यू को एक ऐरे के रूप में आउटपुट करना होगा। उदाहरण के लिए, अगर इनपुट है [[3,4], [2,3], [1,2]], तो आउटपुट होगा [-1, 0, 1], क्योंकि [3, 4] के लिए ऐसा कोई राइट इंटरवल नहीं है, इंटरवल [2,3] के लिए, इंटरवल [3,4] में मिनिमम-"राइट" स्टार्ट पॉइंट है; और [1,2] के लिए, इंटरवल [2,3] में मिनिमम-"राइट" स्टार्ट पॉइंट है।

इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:

  • n := इंटरवल्स ऐरे का साइज, साइज n का एक ऐरे ret बनाएं, और इसे -1 से भरें, एक मैप m बनाएं

  • i को 0 से इंटरवल्स के साइज तक लूप करें:

    • अगर intervals[i][0] m में है, तो अगले इंटरवल पर जाएं

    • m[intervals[i][0]] := i + 1

  • i को n-1 से i >= 0 तक डाउनटू लूप करें:

    • it := उस की-वैल्यू पेयर को पॉइंट करें जिसमें सबसे छोटी की हो, लेकिन intervals[i][1] से छोटी न हो

    • अगर it का वैल्यू 0 है, तो अगले इटरेशन पर जाएं

    • ret[i] := it का वैल्यू - 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:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        int n = intervals.size();
        vector <int> ret(n, -1);
        map <int, int> m;
        for(int i = 0; i < intervals.size(); i++){
            if(m.count(intervals[i][0])) continue;
            m[intervals[i][0]] = i + 1;
        }
        for(int i = n - 1; i >= 0; i--){
            map <int, int> :: iterator it = m.lower_bound(intervals[i][1]);
            if(it->second == 0) continue;
            ret[i] = it->second - 1;
        }
        return ret;
    }
};

int main(){
    vector<vector<int>> v = {{3,4},{2,3},{1,2}};
    Solution ob;
    print_vector(ob.findRightInterval(v));
}

इनपुट

[[3,4],[2,3],[1,2]]

आउटपुट

[-1,0,1]

  1. C++ में त्रिभुज का परिमाप खोजें C++ में त्रिभुज का परिमाप खोजें

    इस समस्या में, हम त्रिभुज का परिमाप, विभिन्न प्रकार के त्रिभुजों के परिमाप का सूत्र और उन्हें खोजने के लिए प्रोग्राम देखेंगे।परिमाप को आकृति के चारों ओर की कुल दूरी के रूप में परिभाषित किया गया है। मूल रूप से, यह दी गई आकृति की सभी भुजाओं का योग है।त्रिभुज का परिमापत्रिभुज का परिमाप इसकी सभी तीन भुज

  1. C++ में बाइनरी ट्री में दी गई कुंजी का अगला दायां नोड ढूंढना C++ में बाइनरी ट्री में दी गई कुंजी का अगला दायां नोड ढूंढना

    इस समस्या में, हमें एक बाइनरी ट्री BT और एक कुंजी मान दिया जाता है। हमारा कार्य दी गई कुंजी का अगला दायां नोड ढूंढना है।बाइनरी ट्री डेटा स्टोरेज उद्देश्यों के लिए उपयोग की जाने वाली एक विशेष डेटा संरचना है।आइए एक उदाहरण से समस्या को समझते हैं,इनपुटkey = 4आउटपुट5व्याख्यानोड 4 के बगल में स्थित तत्व 5

  1. C++ में डुप्लिकेट उपट्री ढूंढना C++ में डुप्लिकेट उपट्री ढूंढना

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें सभी डुप्लिकेट उपट्री ढूंढने हैं। इसलिए प्रत्येक प्रकार के डुप्लिकेट उपट्री के लिए, हमें उनमें से किसी एक का रूट नोड लौटाना है। मान लीजिए हमारे पास ऐसा ट्री है: डुप्लिकेट उपट्री हैं: हल का दृष्टिकोण इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे: