የረጅም ጊዜ ትክክለኛ ቅንፍ ውጤት ለማግኘት የክልል ጥያቄዎች  


የችግር ደረጃ ጠንካራ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን የኮድ ቁጥር google የ PayPal በ Uber
ሰልፍ ክምር

የአንዳንድ ቅንፎች ቅደም ተከተል ቅደም ተከተል ይሰጥዎታል ፣ በሌላ አነጋገር እንደ ‹(› እና ‹)› ያሉ ቅንፎች ይሰጡዎታል እናም እንደ መነሻ እና የማጠናቀቂያ ነጥብ የጥያቄ ክልል ይሰጥዎታል ፡፡ ችግሩ “ረዘም ላሉት ትክክለኛ ቅንፍ ቅደም ተከተል የክልል ጥያቄዎች” በተጠቀሰው የመጠየቂያ ክልል ውስጥ ልክ እንደ “() ()” ፣ “(())” ፣ “() ትክክለኛ የቅንፍ ተከታይ ወይም ሚዛናዊ ቅንፍ ቅንፎች ከፍተኛውን ርዝመት ለማወቅ ይጠይቃል። (())) ”ወዘተ

ለምሳሌ  

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. ጥያቄውን እንደ StartPoint እና EndPoint ይውሰዱት።
    1. የመክፈቻ ቁልፎች [startingPoint-1] = የመክፈቻ ቁልፎች [startingPoint] ከሆነ ያረጋግጡ
      1. መመለስ (ዝግ ብራኮች [EndPoint] - የመክፈቻ ቁልፎች [startingPoint]) * 2.
    2. ሌላ መመለሻ (ዝግ ብራኮች [EndPoint] - የመክፈቻ ብሩኮች [ጅምር ቦታ] + 1) * 2።

ማስረጃ  

የ ‹(እና›) ›ቅንፍ አይነት የሚገኝበት ፣ እና የተለያዩ መጠይቆች የተሰጡበት ተከታታይ ቅንፎች ተከታታይነት ተሰጥቶናል ፡፡ መጠይቆች የሚሠጡት በንዑስ ቡድኑ መነሻ እና የማጠናቀቂያ ነጥብ መልክ ነው ፡፡ በተጠቀሰው ክልል ውስጥ ትክክለኛውን ወይም የተመጣጠነ ቅንፍ ከፍተኛውን ርዝመት ለማወቅ እንጠየቃለን። ትክክለኛ ወይም ሚዛናዊ ቅንፎች የመክፈቻ ወይም የመዝጊያ ቅንፎችን እንደ እኩል አይቆጠሩም ፡፡ እኛ ግን ክልል ተሰጥቶናል ፣ በተከታታይ ቅንፎች አማካኝነት የሚቻለውን ከፍተኛውን ርዝመት መፈለግ አለብን ፡፡

ተመልከት
የሁሉም ጎዶሎ ርዝመት ርዝመት ሱባራይስ ሌትኮድ መፍትሔ ድምር

ለማወቅ ፣ እንደ የውሂብ አወቃቀር ያለ ቁልል ጠቃሚ ይሆናል። ከጀመርነው ቦታ ማግኘት እንድንችል ሁሉንም የመክፈቻ ቅንፎችን ወደ ቁልቁል እንገፋፋቸዋለን ፡፡ የአሁኑ ቅንፍ የመክፈቻ ቅንፍ ካልሆነ። ተጨማሪ ሥራዎችን ለማከናወን ቁልል ባዶ መሆን እንደሌለበት ማረጋገጥ አለብን ፡፡ በእርግጥ እሱ የመዝጊያ ቅንፍ ይሆናል። የመክፈቻ ቅንፍ ካልሆነ ያንን የመዝጊያ ቅንፍ መረጃ ጠቋሚ እንደ 1. ምልክት እናደርጋለን በሚቀጥለው ደረጃ ደግሞ የቁልል መጠን እናገኛለን እና ያንን መጠን እንደ ኢንዴክስ እንይዛለን እና ያንን መረጃ ጠቋሚ እንደ 1 የመክፈቻ ቅንፎች ፣ እና የቁልል ንጥረ ነገር ብቅ ይበሉ ፡፡ የሕብረቁምፊውን ርዝመት ይጓዙ እና የእያንዳንዱን እሴት ያጠቃልሉ መክፈቻዎችመዝጊያዎች እና ድምርውን በእያንዳንዱ መረጃ ጠቋሚ ላይ ያከማቹ።

ጥያቄዎቹን እንደ ግብዓት ይውሰዱ እና በ ውስጥ ያረጋግጡ መዝጊያዎች የመነሻ ነጥብ እሴት ከቀዳሚው እሴት ጋር እኩል ከሆነ መክፈቻዎች በመቀጠልም የመዝጊያ ቁልፎችን (EndPoint) ልዩነት ሁለት እጥፍ አድርገው ይመልሱ - የመክፈቻ ብራኮች [startingPoint]። አለበለዚያ ቁጥሩን እንደ መዝጊያ ቁልፎች (EndingPoint) ልዩነት ሁለት እጥፍ ይመልሱ - የመክፈቻ ብራኮች [startingPoint] + 1. እኛ የምንፈልገውን መልስ እናገኛለን

ኮድ  

ለ “ረዥሙ ትክክለኛ ቅንፍ ተከታይ” የክልል ጥያቄዎችን ለመመለስ የ C ++ ኮድ

#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) ለእያንዳንዱ ጥያቄ ለተደረገ ፡፡ ግን ቅድመ ማስላት ይጠይቃል ኦ (n + q) ጊዜ ስለዚህ የአልጎሪዝም አጠቃላይ የጊዜ ውስብስብነት መስመራዊ ነው።

ተመልከት
የሃኖይ ግንብ

የቦታ ውስብስብነት

ሆይ (n) የት “N” የሕብረቁምፊው ርዝመት ነው። የመክፈቻውን ቅንፍ እና የመዝጊያ ቅንፍ ቆጠራን ለማከማቸት ሁለት ድርድሮችን ስለፈጠርን። የቦታ ውስብስብነት መስመራዊ ነው።