सब भन्दा लामो सही कोष्ठक उप-अनुक्रमको लागि दायरा क्वेरीहरू


कठिनाई तह हार्ड
बारम्बार सोधिन्छ अमेजन CodeNation गुगल PayPal Uber
एरे थाक

तपाईंलाई केही कोष्ठक अनुक्रमको क्रम दिइन्छ, अर्को शब्दमा, तपाईंलाई '(' र ') जस्तै कोष्ठक दिईन्छ र तपाईंलाई क्वेरी दायरा सुरूवात बिन्दु र अन्त्य बिन्दुको रूपमा दिइन्छ। समस्या "सबैभन्दा लामो सही कोष्ठक उपसंक्रमको लागि दायरा क्वेरीहरू" दिईएको क्वेरी दायरा भित्र "() () (") "," (()) "," ("(" (()) "आदि।

उदाहरणका

String s = “()())()(())( ”
startingPoint = 4
endingPoint = 8
2

स्पष्टीकरण

केवल सही कोष्ठकहरू अनुक्रमणिका and र at मा छन्।

सब भन्दा लामो सही कोष्ठक उप-अनुक्रमको लागि दायरा क्वेरीहरू

 

अल्गोरिदम

  1. घोषणा गर्नुहोस् थाक.
  2. पूर्ण ट्राभर्स string र सबै शुरुवात कोष्ठक स्ट्याकमा धकेल्नुहोस्।
    1. यदि यो कोष्ठक खुलिरहेको छैन भने जाँच गर्नुहोस् यदि स्ट्याक खाली छैन भने, तब त्यो सूचकांक १ को रूपमा चिन्ह लगाउनुहोस्।
      1. स्ट्याकको आकार पाउनुहोस् र १ लाई सूचकांक चिन्ह लगाउनुहोस्, र शीर्ष तत्वलाई स्ट्याकबाट पप गर्नुहोस्।
    2. यदि स्ट्याक खाली छ भने त्यो सूचकांक बन्द कोष्ठक ० को रूपमा चिन्ह लगाउनुहोस्।
  3. स्ट्रिंगको लम्बाइ सम्म ट्रान्स गर्नुहोस् र निम्न तत्वको प्रत्येक जोड।
    1. क्लोजब्रेकेटहरू [i] = बन्दब्रेकेटहरू [i] + बन्दब्रेकेटहरू [i-1]
    2. उद्घाटन कोष्ठक [i] = उद्घाटन कोष्ठक [i] + उद्घाटन कोष्ठक [i-1]
  4. क्वेरीलाई सुरूवात र अन्त्य पोइन्टको रूपमा लिनुहोस्।
    1. यदि ओपनब्रेकेटहरू [आरम्भिक प्वाइन्ट १ - १] = ओपनब्रेकेटहरू [आरम्भिकरण]
      1. फिर्ती (बन्दब्रेकेटहरू [अन्डिंगपोइन्ट]] - ओपनब्रेकेट्स [आरम्भ पोइन्ट]] * २।
    2. अर्को फिर्ती (बन्दब्रेकेटहरू [अन्डिंगपोइन्ट] - ओपनब्रेकेट्स [सुरूवाती प्वाइन्ट] + १) * २।

स्पष्टीकरण

हामीलाई ब्रैकेटको अनुक्रमको स्ट्रिंग दिइयो, जसमा '(' र ')' प्रकारको कोष्ठकहरू उपस्थित छन्, र प्रश्नहरूको दायरा दिइन्छ। क्वेरीहरू सुरूवाती बिन्दु र subarray को अन्त्य बिन्दुको रूपमा दिइन्छ। हामीलाई दिइएको दायरा भित्र सही वा सन्तुलित कोष्ठको अधिकतम लम्बाइ पत्ता लगाउन सोधिन्छ। सहि वा सन्तुलित कोष्ठक ब्रेसि opening खोल्ने वा बन्द गर्ने बराबर नम्बरको रूपमा लिन सकिन्छ। तर हामीलाई एउटा दायरा दिइयो, हामीले अधिकतम लम्बाइ पत्ता लगाउनु पर्छ जुन ब्राकेटको सही अनुक्रमको साथ सम्भव छ।

खोज्नको लागि, स्ट्याक जस्तो डाटा संरचना लाभदायक हुनेछ। हामी सबै उद्घाटन कोष्ठकलाई स्ट्याकमा धकेल्दैछौं ताकि हामी कहाँबाट सुरु गर्न सक्दछौं। यदि हाल कोष्ठक एक खुल्ने कोष्ठक छैन भने। हामीले जाँच गर्नुपर्नेछ कि स्ट्याक अर्को अपरेसनहरू गर्न खाली हुनु हुँदैन। अवश्य पनि, यो बन्द हुने कोष्ठक हुनेछ। यदि यो खोलिएको ब्र्याकेट होईन भने, त्यसपछि हामी क्लोजिंग कोष्ठक सूचकांक १ को रूपमा चिन्ह लगाउँछौं। र अर्को चरणमा हामी स्ट्याकको साइज पाउनेछौं र त्यो साइजलाई इन्डेक्सको रूपमा व्यवहार गर्नेछौं र त्यो इन्डेक्स १ को रूपमा चिन्हित गर्नेछौं। ओपनब्रेकेटहरू, र स्ट्याकको तत्व पप गर्नुहोस्। स्ट्रिंगको लम्बाइ सम्म ट्रान्सभर्स गर्नुहोस्, र प्रत्येक मानको योगफल ओपनब्रेकेटहरूक्लोजिंग ब्रैकेट्स र प्रत्येक सूचकांकमा योग भण्डार गर्नुहोस्।

प्रश्नहरू इनपुटको रूपमा लिनुहोस्, र चेक इन गर्नुहोस् क्लोजिंग ब्रैकेट्स यदि सुरूवात विन्दु मानको अघिल्लो मान बराबर हो ओपनब्रेकेटहरू तब क्लोजिंगब्रेकेट [अन्डिंगपोइन्ट] को फरक दुई पटक नम्बर फिर्ता गर्नुहोस् - ओपनब्रेकेट [सुरूवात बिन्दु]। अन्यथा क्लोजिंग ब्रैकेट्स [अन्डिंगपोइन्ट] को फरक दुई पटक नम्बर फिर्ता गर्नुहोस् - ओपनब्रेकेट्स [सुरुवाती प्वाइन्ट] + १। हामी इच्छित जवाफ पाउनेछौं।

कोड

C ++ कोड दायरा प्रश्नहरूको जवाफ दिनको लागि सबैभन्दा लामो कोष्ठ कोष्ठक subsequence

#include<iostream>
#include<cstring>
#include<stack>

using namespace std;

void correctBracketsLength(int OPENINGBRACKETS[], int CLOSEDBRACKETS[], char* str, int n)
{
    stack<int> STACK;
    int result = 0;
    for (int i = 0; i < n; i++)
    {
        if (str[i] == '(')
            STACK.push(i);
        else
        {
            if (!STACK.empty())
            {
                CLOSEDBRACKETS[i] = 1;
                OPENINGBRACKETS[STACK.top()] = 1;
                STACK.pop();
            }
            else
                CLOSEDBRACKETS[i] = 0;
        }
    }
    for (int i = 1; i < n; i++)
    {
        CLOSEDBRACKETS[i] += CLOSEDBRACKETS[i - 1];
        OPENINGBRACKETS[i] += OPENINGBRACKETS[i - 1];
    }
}
int query(int OPENINGBRACKETS[], int CLOSEDBRACKETS[], int startingPoint, int endingPoint)
{
    if (OPENINGBRACKETS[startingPoint - 1] == OPENINGBRACKETS[startingPoint])
    {
        return (CLOSEDBRACKETS[endingPoint] - OPENINGBRACKETS[startingPoint]) * 2;
    }
    else
    {
        return (CLOSEDBRACKETS[endingPoint] - OPENINGBRACKETS[startingPoint] + 1) * 2;
    }
}
int main()
{
    char str[] = "()())()(())(";
    int n = strlen(str);

    int CLOSEDBRACKETS[n + 1] = { 0 };
    int OPENINGBRACKETS[n + 1] = { 0 };

    correctBracketsLength(OPENINGBRACKETS, CLOSEDBRACKETS, str, n);

    int startingPoint = 4, endingPoint = 8;

    cout << "Maximum Length within "
         << startingPoint << " and " << endingPoint << " = "
         << query(OPENINGBRACKETS, CLOSEDBRACKETS, startingPoint, endingPoint) << endl;

    return 0;
}
Maximum Length within 4 and 8 = 2

सबै भन्दा लामो सही कोष्ठक उप-अनुच्छेदको लागि दायरा प्रश्नहरूको उत्तर दिन जाभा कोड

import java.util.*;

class LongestCorrectBracket
{
    public static void correctBracketsLength(int OPENINGBRACKETS[], int CLOSEDBRACKETS[], String str, int n)
    {
        Stack<Integer> STACK = new Stack<>();;

        for(int i = 0; i < n; i++)
        {
            if (str.charAt(i) == '(')
                STACK.add(i);
            else
            {
                if (!STACK.isEmpty())
                {
                    CLOSEDBRACKETS[i] = 1;
                    OPENINGBRACKETS[STACK.peek()] = 1;
                    STACK.pop();
                }
                else
                    CLOSEDBRACKETS[i] = 0;
            }
        }
        for(int i = 1; i < n; i++)
        {
            CLOSEDBRACKETS[i] += CLOSEDBRACKETS[i - 1];
            OPENINGBRACKETS[i] += OPENINGBRACKETS[i - 1];
        }
    }
    static int query(int OPENINGBRACKETS[], int CLOSEDBRACKETS[], int startingPoint, int endingPoint)
    {
        if (OPENINGBRACKETS[startingPoint - 1] == OPENINGBRACKETS[startingPoint])
        {
            return (CLOSEDBRACKETS[endingPoint] - OPENINGBRACKETS[startingPoint]) * 2;
        }
        else
        {
            return (CLOSEDBRACKETS[endingPoint] - OPENINGBRACKETS[startingPoint] + 1) * 2;
        }
    }
    public static void main(String[] args)
    {
        String str = "()())()(())(";
        int n = str.length();

        int CLOSEDBRACKETS[] = new int[n + 1];
        int OPENINGBRACKETS[] = new int[n + 1];

        correctBracketsLength(OPENINGBRACKETS, CLOSEDBRACKETS, str, n);

        int startingPoint = 4, endingPoint = 8;
        System.out.print("Maximum Length within " +
                         startingPoint + " and " + endingPoint +
                         " = " + query(OPENINGBRACKETS, CLOSEDBRACKETS, startingPoint,
                                       endingPoint) + "\n");
    }
}
Maximum Length within 4 and 8 = 2

जटिलता विश्लेषण

समय जटिलता

O (१) प्रदर्शन गरिएको प्रत्येक क्वेरीको लागि। तर पूर्वनिर्धारण आवश्यक छ O (n + q) समय यस प्रकार एल्गोरिथ्मको कुल समय जटिलता रेखीय हो।

ठाउँ जटिलता

ऊ) जहाँ "N" स्ट्रि ofको लम्बाइ हो। किनकि हामीले खोलिएको कोष्ठण र बन्द कोष्ठ गणनाको लागि दुई एर्रेहरू सिर्जना गरेका छौं। ठाउँ जटिलता रैखिक छ।