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

C++ में शब्द लंबाई का अधिकतम गुणनफल


मान लीजिए हमारे पास words नामक एक स्ट्रिंग सरणी है, length(word[i]) * length(word[j]) का अधिकतम मान ढूंढें जहां दो शब्द सामान्य अक्षर साझा नहीं करेंगे। हम मान सकते हैं कि प्रत्येक शब्द में केवल लोअरकेस अक्षर होंगे। यदि ऐसी कोई दो शब्द मौजूद नहीं हैं, तो 0 लौटाएं।

उदाहरण के लिए, यदि इनपुट ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"] जैसा है, तो आउटपुट 16 होगा, क्योंकि दो शब्द "abcw", "xtfn" हो सकते हैं।

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

  • getRev() नामक एक विधि परिभाषित करें, यह x इनपुट के रूप में लेगा
  • ret := 0
  • i को 0 से 25 तक लूप करें
    • यदि x / (2^i) सम है, तो ret := ret OR 2^i
  • ret लौटाएं
  • मुख्य विधि से, निम्नलिखित करें:
    • m नामक एक मैप बनाएं n := words सरणी का आकार
    • i को 0 से n - 1 तक लूप करें
      • s := words[i], key := 0
      • j को 0 से s के आकार तक लूप करें
        • key := key OR 2^(s[j] - 'a' का ASCII)
      • m[i] := key
    • ret := 0
    • i को 0 से words के आकार - 1 तक लूप करें
      • j को i + 1 से words के आकार - 1 तक लूप करें
        • यदि m[i] AND m[j] = 0, तो ret := word[i] का आकार * word[j] का आकार का अधिकतम
    • ret लौटाएं

    उदाहरण (C++)

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

    #include <bits/stdc++.h> using namespace std; class Solution {    public:    int getRev(int x){       int ret = 0;       for(int i = 0; i <= 25 ; i++){          if(!((x >> i) & 1)){             ret |= (1 << i);          }       }       return ret;    }    int maxProduct(vector<string>& words) {       unordered_map <int, int> m;       int n = words.size();       for(int i = 0; i < n; i++){          string s = words[i];          int key = 0;          for(int j = 0; j < s.size(); j++){             key |= 1 << (s[j] - 'a');          }          m[i] = key;       }       int ret = 0;       for(int i = 0; i < words.size(); i++){          for(int j = i + 1; j < words.size(); j++){             if((m[i] & m[j]) == 0){                //cout << i << " " << j << endl;                ret = max(ret, (int)words[i].size() * (int)words[j].size());             }          }       }       return ret;    } }; main(){    Solution ob;    vector<string> v = {"abcw","baz","foo","bar","xtfn","abcdef"};    cout << (ob.maxProduct(v)); }

    इनपुट

    ["abcw","baz","foo","bar","xtfn","abcdef"]

    आउटपुट

    16

  1. C++ में BK ट्री परिचय C++ में BK ट्री परिचय

    BK ट्री या बर्कहार्ड ट्री (Burkhard tree) एक प्रकार की डेटा संरचना है जिसका उपयोग आमतौर पर लेवेंश्टाइन दूरी (Levenshtein distance) के आधार पर स्पेल चेक करने के लिए किया जाता है। इसका उपयोग स्ट्रिंग मिलान के लिए ऑटोकरेक्ट फीचर बनाने के लिए भी किया जाता है। मान लें कि हमारे पास एक डिक्शनरी में कुछ शब

  1. C++ में ट्री में दो गैर-प्रतिच्छेदी पथों का अधिकतम गुणनफल C++ में ट्री में दो गैर-प्रतिच्छेदी पथों का अधिकतम गुणनफल

    इस समस्या में, हमें n नोड्स के साथ एक अविभाजित कनेक्टेड ट्री T दिया गया है। हमारा कार्य C++ में ट्री में दो गैर-प्रतिच्छेदी पथों का अधिकतम गुणनफल ढूंढने के लिए एक प्रोग्राम बनाना है। समस्या विवरण - ट्री में दो गैर-प्रतिच्छेदी पथों का अधिकतम गुणनफल ढूंढने के लिए। हम सभी गैर-प्रतिच्छेदी पथ ढूंढेंगे औ

  1. C++ में अविकलित ग्राफ में सभी चक्रों की लंबाई का गुणनफल C++ में अविकलित ग्राफ में सभी चक्रों की लंबाई का गुणनफल

    हमें इनपुट के रूप में अविकलित और अवेटेड ग्राफ दिया गया है और कार्य दिए गए ग्राफ में बने चक्रों का गुणनफल खोजना और परिणाम प्रदर्शित करना है।उदाहरणइनपुटदिए गए आंकड़े में, 8 नोड्स हैं और उनमें से 5 नोड्स 1, 6, 3, 5, 8 सहित चक्र बना रहे हैं और बाकी नोड्स चक्र में शामिल नहीं हैं। तो, चक्र की लंबाई 5 है क