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

C++ में बाइनरी स्ट्रिंग में शून्य और एक के अधिकतम अंतर


दिया गया कार्य एक दी गई बाइनरी स्ट्रिंग से एक उप-स्ट्रिंग ढूंढना और फिर शून्य और एक की संख्या के बीच अधिकतम अंतर ढूंढना है।

उदाहरण

इनपुट

str = "100100110"

आउटपुट

2

व्याख्या

पोजीशन 1 से 5 ("00100") की उप-सरणी में, शून्य और एक के बीच अंतर = 4 - 1 = 3 जो पाया जा सकने वाला अधिकतम है।

इनपुट

str = "00000"

आउटपुट

5

नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है

  • main() फ़ंक्शन में बाइनरी स्ट्रिंग संग्रहीत करने के लिए एक स्ट्रिंग str बनाएं। साथ ही स्ट्रिंग का आकार संग्रहीत करने के लिए एक चर int size आरंभ करें और दोनों को Max() फ़ंक्शन में पास करें।
  • Max() फ़ंक्शन में पहले जांचें कि क्या सभी तत्व 1 हैं One() फ़ंक्शन को कॉल करके।
  • One() फ़ंक्शन bool प्रकार का बनाएं और अंदर int O = 0 चर बनाएं।
  • i = 0 से i < str.size() तक लूप करें और यदि str[i] == 1 तो चर O में 1 जोड़ें।
  • लूप के बाहर, जांचें कि क्या (O == size)। यदि हां, तो true वापस करें।
  • Max() फ़ंक्शन में वापस यदि One() फ़ंक्शन ने true वापस किया तो, उत्तर के रूप में -1 वापस करें।
  • अन्यथा लंबाई ढूंढने के लिए आगे बढ़ें। एक सरणी int a[100] = { 0 } आरंभ करें।
  • i = 0 से i < size तक लूप करें और a[i] = (str[i] == '0' ? 1 : -1) रखें और str के प्रत्येक तत्व की इस तरह जांच करें।
  • लूप के बाहर, एक और सरणी int arr[100][3] आरंभ करें और memset(arr, -1, sizeof arr) का उपयोग करके इसके सभी तत्वों को -1 से बदलें और अंत में Length(a, str, size, 0, 0, arr) कॉल करें।
  • Length() फ़ंक्शन में, पहले जांचें कि क्या (i >= size), यदि हां, तो इसका मतलब है कि स्ट्रिंग समाप्त हो गई है और 0 वापस करें।
  • फिर जांचें कि क्या (arr[i][s] != -1)। यदि हां, तो इसका मतलब है कि स्थिति पहले ही गणना की जा चुकी है और arr[i][s] वापस करें।
  • फिर जांचें कि क्या (s == 0)। यदि हां, तो arr[i][s] = max(a[i] + Length(a, str, size, i + 1, 1, arr), Length(a, str, size, i + 1, 0, arr)) वापस करें।
  • अन्यथा arr[i][s] = max(a[i] + Length(a, str, size, i + 1, 1, arr), 0) वापस करें।

कार्यक्रम उदाहरण

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

bool One(string str, int size){
    int O = 0;
    for (int i = 0; i < str.size(); i++)
        O += (str[i] == '1');
    return (O == size);
}

int Length(int a[], string str, int size, int i, int s, int arr[][3]){
    // यदि स्ट्रिंग समाप्त हो गई।
    if (i >= size)
        return 0;
    // यदि पहले से गणना की गई।
    if (arr[i][s] != -1)
        return arr[i][s];
    if (s == 0)
        return arr[i][s] = max(a[i] + Length(a, str, size, i + 1, 1, arr), Length(a, str, size, i + 1, 0, arr));
    else
        return arr[i][s] = max(a[i] + Length(a, str, size, i + 1, 1, arr), 0);
}

int Max(string str, int size){
    // जांचें कि क्या सभी तत्व 1 हैं
    if (One(str, size))
        return -1;
    // लंबाई ढूंढना
    int a[100] = { 0 };
    for (int i = 0; i < size; i++)
        a[i] = (str[i] == '0' ? 1 : -1);
    int arr[100][3];
    memset(arr, -1, sizeof arr);
    return Length(a, str, size, 0, 0, arr);
}

// main फ़ंक्शन
int main(){
    string str = "100100110";
    int size = 9;
    cout << Max(str, size);
    return 0;
}

आउटपुट

3
  1. C++ में नोड और पूर्वज के बीच अधिकतम अंतर C++ में नोड और पूर्वज के बीच अधिकतम अंतर

    मान लीजिए हमारे पास एक बाइनरी ट्री की रूट है, हमें अधिकतम मान V ढूंढना होगा जिसके लिए अलग-अलग नोड्स A और B मौजूद हैं जहां V = |A का मान - B का मान| और A, B का पूर्वज है। इसलिए यदि ट्री इस तरह है: तो आउटपुट 7 होगा। पूर्वज नोड अंतर इस तरह हैं: [(8 - 3), (7 - 3), (8 - 1), (10-13)], उनमें से (8 - 1

  1. - C++ स्ट्रिंग कॉन्स्टेंट्स और कैरेक्टर कॉन्स्टेंट्स में अंतर

    C++ में, सिंगल कोट्स में एक कैरेक्टर एक कैरेक्टर लिटरल है। इसका प्रकार char है। उदाहरण के लिए, a ASCII आधारित सिस्टम पर मान 97 के साथ char प्रकार का है। डबल कोट्स में एक कैरेक्टर या कैरेक्टर्स की स्ट्रिंग एक स्ट्रिंग लिटरल दर्शाती है। इसका प्रकार const char[] है और यह स्ट्रिंग की लंबाई + 1 के आकार

  1. - C++ में रिलेशनल ऑपरेटर (==) और std::string::compare() में अंतर

    रिलेशनल ऑपरेटर == और std::string::compare() के बीच केवल एक अंतर है। वह है रिटर्न वैल्यू। आंतरिक रूप से, string::operator==() string::compare() का उपयोग कर रहा है। रिलेशनल ऑपरेटर (==) एक बूलियन लौटाता है जो केवल यह दर्शाता है कि 2 स्ट्रिंग्स समान हैं या नहीं, जबकि compare एक इंटीजर लौटाता है जो दर्श