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

C++ में फलों को टोकरियों में डालना


मान लीजिए हमारे पास पेड़ों की एक पंक्ति है, i-वां पेड़ tree[i] प्रकार का फल पैदा करता है। हम अपनी पसंद के किसी भी पेड़ से शुरू कर सकते हैं, फिर बार-बार ये चरण करें:

  • इस पेड़ से एक फल अपनी टोकरियों में जोड़ें। यदि कोई मौका नहीं है, तो रुकें।
  • वर्तमान पेड़ के दाएं अगले पेड़ पर जाएं। यदि दाएं कोई पेड़ नहीं है, तो रुकें।

हमारे पास दो टोकरियां हैं, और प्रत्येक टोकरी किसी भी मात्रा में फल ले जा सकती है, लेकिन हम चाहते हैं कि प्रत्येक टोकरी केवल एक प्रकार का फल ले जाए। हमें इस प्रक्रिया से एकत्र किए जा सकने वाले फलों की कुल मात्रा ढूंढनी है? उदाहरण के लिए, यदि पेड़ [0, 1, 2, 2] जैसे हैं, तो आउटपुट 3 होगा। हम [1,2,2] एकत्र कर सकते हैं, यदि हम पहले पेड़ से शुरू करते हैं, तो हम केवल [0, 1] एकत्र करेंगे।

हल करने के चरण

  • n := tree का आकार, j := 0, ans := 0
  • एक मैप m बनाएं
  • i को 0 से n-1 तक लूप करें
    • m[tree[i]] को 1 से बढ़ाएं
    • जब तक m का आकार > 2 और j <= i
      • m[tree[j]] को 1 से घटाएं
      • यदि m[tree[j]] = 0, तो tree[j] को m से हटाएं
      • j को 1 से बढ़ाएं
    • ans := max(i - j + 1, ans)
  • ans वापस करें

उदाहरण

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int totalFruit(vector<int>& tree) {       int n = tree.size();       int j = 0;       map <int, int> m;       int ans = 0;       for(int i = 0; i < n; i++){          m[tree[i]] += 1;          while(m.size() > 2 && j <= i){             m[tree[j]]--;             if(m[tree[j]] == 0)m.erase(tree[j]);             j++;          }          ans = max(i - j + 1, ans);       }       return ans;    } }; main(){    vector<int> v = {3,3,3,1,2,1,1,2,3,3,4};    Solution ob;    cout <<(ob.totalFruit(v)); }

इनपुट

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

आउटपुट

5
  1. C++ में एक सेट को k उपसमुच्चयों में विभाजित करने के तरीकों की संख्या गिनें C++ में एक सेट को k उपसमुच्चयों में विभाजित करने के तरीकों की संख्या गिनें

    समस्या विवरण दो संख्याएं e और p दी गई हैं। लक्ष्य उन तरीकों की संख्या गिनना है जिनसे हम एक सेट के e तत्वों को p पार्टीशन/उपसमुच्चयों में विभाजित कर सकते हैं। उदाहरण इनपुट e=4 p=2 आउटपुट सेट को k उपसमुच्चयों में विभाजित करने के तरीकों की संख्या: 7 व्याख्या यदि तत्व हैं: a b c d तो उन्हें 2 पार्टीशन

  1. C++ में बोर्ड को वर्गों में काटने की न्यूनतम लागत C++ में बोर्ड को वर्गों में काटने की न्यूनतम लागत

    अवधारणा मान लीजिए लंबाई p और चौड़ाई q का एक बोर्ड दिया गया है, हमें इस बोर्ड को p*q वर्गों में तोड़ना है ताकि तोड़ने की लागत न्यूनतम हो। इस बोर्ड के लिए, प्रत्येक किनारे के लिए काटने की लागत दी जाएगी। संक्षेप में, हमें काटने का ऐसा क्रम चुनना है जिससे लागत न्यूनतम हो। उदाहरण उपरोक्त बोर्ड को वर्गो

  1. C++ में Insert into a Binary Search Tree C++ में Insert into a Binary Search Tree

    मान लीजिए हमारे पास एक बाइनरी सर्च ट्री है। हमें केवल एक विधि लिखनी है, जो दिए गए नोड को पैरामीटर के रूप में सम्मिलन ऑपरेशन करती है। हमें ध्यान रखना होगा कि ऑपरेशन के बाद, ट्री BST भी बनी रहे। इसलिए यदि ट्री इस तरह है -यदि हम 5 सम्मिलित करते हैं, तो ट्री इस तरह होगी -इसे हल करने के लिए, हम इन चरणों