மிக நீண்ட சரியான அடைப்புக்குறிக்கான வரம்பு வினவல்கள்


சிரமம் நிலை கடின
அடிக்கடி கேட்கப்படுகிறது அமேசான் கோட்நேஷன் கூகிள் பேபால் கிழித்து
அணி ஸ்டேக்

சில அடைப்புக்குறிகளின் தொடர்ச்சியை உங்களுக்கு வழங்கியுள்ளீர்கள், வேறுவிதமாகக் கூறினால், உங்களுக்கு '(' மற்றும் ')' போன்ற அடைப்புக்குறிப்புகள் வழங்கப்படுகின்றன, மேலும் உங்களுக்கு ஒரு தொடக்க புள்ளியாகவும் இறுதி புள்ளியாகவும் வினவல் வரம்பு வழங்கப்படுகிறது. “மிக நீண்ட சரியான அடைப்புக்குறி வரம்பிற்கான வரம்பு வினவல்கள்” சிக்கல் கொடுக்கப்பட்ட வினவல் வரம்பிற்குள் “() ()”, “(())”, “(” போன்ற சரியான அடைப்புக்குறி அடுத்தடுத்த அல்லது சமச்சீர் அடைப்பு அடைப்புக்குறிகளின் அதிகபட்ச நீளத்தைக் கண்டுபிடிக்க கேட்கிறது. (())) ”போன்றவை.

உதாரணமாக

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

விளக்கம்

சரியான அடைப்புக்குறிப்புகள் குறியீட்டு 5 மற்றும் 6 இல் உள்ளன.

மிக நீண்ட சரியான அடைப்புக்குறிக்கான வரம்பு வினவல்கள்

 

அல்காரிதம்

  1. ஒரு அறிவிக்கவும் ஸ்டேக்.
  2. முழுமையான பயணிக்கவும் சரம் மற்றும் அனைத்து தொடக்க அடைப்புக்குறிகளையும் அடுக்கில் தள்ளுங்கள்.
    1. இது அடைப்புக்குறியைத் திறக்கவில்லை என்றால், அடுக்கு காலியாக இல்லையா என்பதைச் சரிபார்க்கவும், பின்னர் அந்த குறியீட்டை 1 எனக் குறிக்கவும்.
      1. அடுக்கின் அளவைப் பெற்று, அந்த குறியீட்டை 1 எனக் குறிக்கவும், மேலும் மேல் உறுப்பை அடுக்கிலிருந்து பாப் செய்யவும்.
    2. அடுக்கு காலியாக இருந்தால், அந்த குறியீட்டை மூடிய அடைப்புக்குறி 0 எனக் குறிக்கவும்.
  3. சரத்தின் நீளம் வரை பயணித்து ஒவ்வொரு உறுப்புகளையும் பின்வருமாறு தொகுக்கவும்.
    1. மூடிய ப்ராக்கெட்டுகள் [i] = மூடிய ப்ராக்கெட்டுகள் [i] + மூடிய ப்ராக்கெட்டுகள் [i-1]
    2. திறப்பு ப்ராக்கெட்டுகள் [i] = திறப்பு பிராக்கெட்டுகள் [i] + திறப்பு பிராக்கெட்டுகள் [i-1]
  4. வினவலை ஸ்டார்ட் பாயிண்ட் மற்றும் எண்டிங் பாயிண்ட் என எடுத்துக் கொள்ளுங்கள்.
    1. திறப்பு பிராக்கெட்டுகள் [தொடக்க புள்ளி -1] = திறப்பு பிராக்கெட்டுகள் [தொடக்கநிலை]
      1. திரும்ப (மூடிய பிராக்கெட்டுகள் [endPoint] - திறப்பு பிராக்கெட்டுகள் [தொடக்கப்புள்ளி]) * 2.
    2. வேறு வருவாய் (மூடிய பிராக்கெட்டுகள் [endPoint] - திறப்பு பிராக்கெட்டுகள் [தொடக்க புள்ளி] + 1) * 2.

விளக்கம்

அடைப்புக்குறிகளின் வரிசையின் ஒரு சரம் எங்களுக்கு வழங்கப்பட்டுள்ளது, இதில் '(' மற்றும் ')' வகை அடைப்புக்குறிப்புகள் உள்ளன, மேலும் பலவிதமான வினவல்கள் வழங்கப்படுகின்றன. வினவல்கள் ஒரு தொடக்க புள்ளி மற்றும் சப்ரேயின் இறுதி புள்ளி வடிவத்தில் கொடுக்கப்பட்டுள்ளன. கொடுக்கப்பட்ட வரம்பிற்குள் சரியான அல்லது சீரான அடைப்புக்குறிப்பின் அதிகபட்ச நீளத்தைக் கண்டறியும்படி கேட்கப்படுகிறோம். சரியான அல்லது சீரான அடைப்புக்குறிகளை அடைப்புக்குறிகளைத் திறப்பதற்கும் மூடுவதற்கும் சமமானதாகக் கருதலாம். ஆனால் எங்களுக்கு ஒரு வரம்பு வழங்கப்பட்டுள்ளது, சரியான தொடர்ச்சியான அடைப்புக்குறிக்குள் சாத்தியமான அதிகபட்ச நீளத்தை நாம் கண்டுபிடிக்க வேண்டும்.

கண்டுபிடிக்க, தரவு அமைப்பு போன்ற அடுக்கு நன்மை பயக்கும். நாம் அனைத்து தொடக்க அடைப்புகளையும் அடுக்கிற்குள் தள்ளப் போகிறோம், இதன் மூலம் நாம் தொடங்க வேண்டிய இடத்திலிருந்து கண்டுபிடிக்க முடியும். தற்போதைய அடைப்புக்குறி ஒரு தொடக்க அடைப்பு இல்லை என்றால். மேலதிக செயல்பாடுகளைச் செய்வதற்கு அடுக்கு காலியாக இருக்க வேண்டாமா என்பதை நாம் சரிபார்க்க வேண்டும். நிச்சயமாக, இது ஒரு இறுதி அடைப்புக்குறியாக இருக்கும். இது ஒரு தொடக்க அடைப்புக்குறி இல்லையென்றால், அந்த மூடு அடைப்புக்குறி குறியீட்டை 1 எனக் குறிக்கிறோம். அடுத்த கட்டத்தில், அடுக்கின் அளவைப் பெற்று, அந்த அளவை ஒரு குறியீடாகக் கருதி, அந்த குறியீட்டை 1 எனக் குறிப்போம் திறப்பு பிராக்கெட்டுகள், மற்றும் அடுக்கின் உறுப்பை பாப் செய்யவும். சரத்தின் நீளம் வரை பயணித்து, அதன் ஒவ்வொரு மதிப்பையும் தொகுக்கவும் திறப்பு பிராக்கெட்டுகள் மற்றும் மூடுதல்கள் ஒவ்வொரு குறியீட்டிலும் தொகையை சேமிக்கவும்.

வினவல்களை உள்ளீடாக எடுத்து, சரிபார்க்கவும் மூடுதல்கள் தொடக்க புள்ளி மதிப்பு முந்தைய மதிப்புக்கு சமமாக இருந்தால் திறப்பு பிராக்கெட்டுகள் பின்னர் மூடுதலின் [எண்டிங் பாயிண்ட்] - ஓப்பனிங் பிராக்கெட்டுகள் [ஸ்டார்ட் பாயிண்ட்] வித்தியாசத்தின் இரு மடங்காக எண்ணைத் திருப்பி விடுங்கள். மூடுதலின் [எண்டிங் பாயிண்ட்] - ஓப்பனிங் பிராக்கெட்டுகள் [ஸ்டார்ட் பாயிண்ட்] + 1. வித்தியாசத்தை விட இரண்டு மடங்கு எண்ணைத் திருப்பி விடுங்கள்.

குறியீடு

மிக நீண்ட சரியான அடைப்புக்குறிக்கான வரம்பு கேள்விகளுக்கு பதிலளிக்க சி ++ குறியீடு

#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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (1) ஒவ்வொரு வினவலுக்கும். ஆனால் முன் கணிப்பு தேவைப்படுகிறது O (n + q) நேரம். இதனால் வழிமுறையின் மொத்த நேர சிக்கலானது நேரியல் ஆகும்.

விண்வெளி சிக்கலானது

ஓ (n) எங்கே “N” இது சரத்தின் நீளம். தொடக்க அடைப்பை சேமிப்பதற்கும் அடைப்புக்குறி எண்ணிக்கையை மூடுவதற்கும் நாங்கள் இரண்டு வரிசைகளை உருவாக்கியுள்ளோம். விண்வெளி சிக்கலானது நேரியல்.