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

सॉर्टेड III बनाने के लिए कॉलम हटाएं C++ में

मान लीजिए हमारे पास N स्ट्रिंग्स की एक सरणी A है। प्रत्येक स्ट्रिंग लोअरकेस अक्षरों से बनी है, सभी की लंबाई समान है। अब, हम डिलीशन सूचकांकों का कोई भी समुच्चय चुन सकते हैं, और प्रत्येक स्ट्रिंग के लिए, हम उन सूचकांकों पर सभी वर्णों को हटा देंगे। अब मान लीजिए हमने डिलीशन सूचकांकों का एक समुच्चय D लिया है जैसे कि डिलीशन के बाद, अंतिम सरणी का हर तत्व लेक्सिकोग्राफिक क्रम में है।

स्पष्टता के लिए, A[0] लेक्सिकोग्राफिक क्रम में है (यानी A[0][0] <= A[0][1] <= ... <= A[0][n-1]), A[1] लेक्सिकोग्राफिक क्रम में है, और इसी तरह। (यहां n स्ट्रिंग्स का आकार है)। हमें D के आकार का न्यूनतम संभव मान ढूंढना है।

उदाहरण के लिए, यदि इनपुट ["cbcdb","ccbxc"] है, तो आउटपुट 3 होगा।

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

यह कॉलम पर सबसे लंबी बढ़ती हुई उपअनुक्रम (LIS) समस्या है:

  • lis[i] = कॉलम i पर समाप्त होने वाली सबसे लंबी वैध कॉलम अनुक्रम की लंबाई

  • प्रत्येक कॉलम जोड़ी (j, i) के लिए जहां j < i, जांचें कि क्या सभी पंक्तियों के लिए A[k][j] <= A[k][i]

  • यदि वैध है, तो lis[i] = max(lis[i], lis[j] + 1) अपडेट करें

  • उत्तर = कुल_कॉलम - अधिकतम_LIS_लंबाई

उदाहरण

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

class Solution { 
public: 
    int minDeletionSize(vector<string>& A){ 
        int ret = 0; 
        int n = A.size(); 
        int m = A[0].size(); 
        vector<int> lis(m + 1, 1); 
        
        for (int i = 0; i < m; i++) { 
            for (int j = 0; j < i; j++) { 
                bool ok = true; 
                for (int k = 0; k < n; k++) { 
                    if (A[k][j] > A[k][i]) { 
                        ok = false; 
                        break; 
                    } 
                } 
                if (ok) { 
                    lis[i] = max(lis[j] + 1, lis[i]); 
                    ret = max(ret, lis[i]); 
                } 
            } 
        } 
        
        if (ret == 0) return m - 1; 
        return m - ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<string> v = {"cbcdb","ccbxc"}; 
    cout << (ob.minDeletionSize(v)); 
    return 0;
}

इनपुट

{"cbcdb","ccbxc"}

आउटपुट

3
  1. C++ में जंप गेम V C++ में जंप गेम V

    मान लीजिए हमारे पास arr नामक पूर्णांकों की एक सरणी और एक पूर्णांक d है। एक चरण में हम इंडेक्स i से कूद सकते हैं: i + x जहां: i + x < n और x की सीमा 1 से d है। = 0 और x की सीमा 1 से d है। arr[k] हो। हम सरणी के किसी भी इंडेक्स से कूदना शुरू कर सकते हैं। हमें अधिकतम इंडेक्स की संख्या ज्ञात करनी है ज

  1. - C++ में delete() ऑपरेटर

    delete ऑपरेटर का उपयोग मेमोरी को डीएलोकेट करने के लिए किया जाता है। यूजर के पास इस delete ऑपरेटर द्वारा बनाए गए पॉइंटर वेरिएबल को डीएलोकेट करने का विशेषाधिकार होता है। C++ भाषा में delete ऑपरेटर का सिंटैक्स निम्नलिखिक है, delete pointer_variable; आवंटित मेमोरी ब्लॉक को डिलीट करने का सिंटैक्स निम्नलि

  1. - पायथन में कॉलम हटाकर सॉर्ट करना

    मान लीजिए हमारे पास N लोअरकेस अक्षर स्ट्रिंग की एक सरणी है, सरणी का नाम A है, सभी स्ट्रिंग्स की लंबाई समान है। अब, हम डिलीशन इंडेक्स का कोई भी सेट चुन सकते हैं, और प्रत्येक स्ट्रिंग के लिए, हम उन इंडेक्स के सभी वर्णों को हटा देते हैं। उदाहरण के लिए, यदि हमारे पास A जैसे [abcdef,uvwxyz] सरणी है और ड