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

C++ में बढ़ते उपअनुक्रम


मान लीजिए हमारे पास एक पूर्णांक सरणी है, हमारा कार्य दी गई सरणी के सभी संभावित विभिन्न बढ़ते उपअनुक्रमों को ढूंढना है, और एक बढ़ते उपअनुक्रम की लंबाई कम से कम 2 होनी चाहिए। इसलिए यदि सरणी [4,6,7,7] है, तो आउटपुट इस तरह होगा: [[4,6], [4,7], [4,6,7], [4,6,7,7], [6,7], [6,7,7], [7,7], [4,7,7]]।

हल का दृष्टिकोण

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

  • सभी परिणामों को संग्रहीत करने के लिए res नामक एक सरणी परिभाषित करें
  • solve नामक एक विधि बनाएं। यह nums सरणी, start, और temp सरणी लेगा
    • यदि temp का आकार > 1, तो temp को res में डालें
    • visited नामक एक सेट बनाएं
    • i = start से nums का आकार तक:
      • x := nums[i]
      • यदि x, visited सेट में है, तो लूप के अगले भाग को छोड़ें
      • x को visited सेट में डालें
      • यदि temp खाली है या temp का अंतिम तत्व <= x:
        • x को temp में डालें
        • solve(nums, i+1, temp) कॉल करें
        • temp के अंत से एक तत्व हटाएं
  • मुख्य विधि से, solve(nums, 0, temp) कॉल करें
  • res लौटाएं

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

void print_vector(vector<vector<auto>> v){ 
    cout << "["; 
    for(int i = 0; i < v.size(); i++){ 
        cout << "["; 
        for(int j = 0; j < v[i].size(); j++){ 
            cout << v[i][j] << ", "; 
        } 
        cout << "],"; 
    } 
    cout << "]" << endl; 
} 

class Solution { 
public: 
    vector<vector<int>> res; 
    void solve(vector<int>& nums, int start, vector<int> temp){ 
        if(temp.size() > 1){ 
            res.push_back(temp); 
        } 
        set<int> visited; 
        for(int i = start; i < nums.size(); i++){ 
            int x = nums[i]; 
            if(visited.count(x)) continue; 
            visited.insert(x); 
            if(temp.empty() || temp[temp.size() - 1] <= x){ 
                temp.push_back(x); 
                solve(nums, i + 1, temp); 
                temp.pop_back(); 
            } 
        } 
    } 
    vector<vector<int>> findSubsequences(vector<int>& nums) { 
        res.clear(); 
        vector<int> temp; 
        solve(nums, 0, temp); 
        return res; 
    } 
}; 

int main(){ 
    vector<int> v = {5,6,7,8}; 
    Solution ob; 
    print_vector(ob.findSubsequences(v)); 
}

इनपुट

[4,6,7,8]

आउटपुट

[[5, 6, ],[5, 6, 7, ],[5, 6, 7, 8, ],[5, 6, 8, ],[5, 7, ],[5, 7, 8, ],[5, 8, ],[6, 7, ],[6, 7, 8, ],[6, 8, ],[7, 8, ],]

  1. - C++ में संयोजन योग II (Combination Sum II)

    मान लीजिए हमारे पास उम्मीदवार संख्याओं का एक समूह है (सभी तत्व अद्वितीय हैं) और एक लक्ष्य संख्या। हमें उम्मीदवारों में उन सभी अद्वितीय संयोजनों को ढूंढना है जहां उम्मीदवार संख्याओं का योग दिए गए लक्ष्य के बराबर हो। वही संख्या उम्मीदवारों से एक से अधिक बार नहीं चुनी जाएगी। यदि तत्व [2,3,6,7,8] हैं औ

  1. - C++ में 3Sum Closest समस्या

    मान लीजिए हमारे पास n पूर्णांकों वाली एक सरणी nums और एक लक्ष्य है। हमें nums में तीन पूर्णांक ढूंढने हैं जिनका योग लक्ष्य के सबसे करीब हो। हम तीन पूर्णांकों का योग लौटाएंगे। हम यह मान ले सकते हैं कि प्रत्येक इनपुट का ठीक एक समाधान होगा। तो यदि दी गई सरणी [-1,2,1,-4] जैसी है और लक्ष्य 1 है, तो ट्रिप

  1. - C++ में कॉम्बिनेशन्स

    मान लीजिए हमारे पास दो पूर्णांक n और k हैं। हमें 1 ... n में से k संख्याओं के सभी संभावित संयोजन ढूंढने हैं। इसलिए यदि n = 4 और k = 2, तो संयोजन [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] होंगे।इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -हम इसे हल करने के लिए पुनरावर्ती फ़ंक्शन का उपयोग करेंगे। solve