වරහන් වර්‍ග ලීට්කෝඩ් විසඳුමේ උපරිම කැදැල්ල ගැඹුර


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ බ්ලූම්බර්ග්
String

ගැටළු ප්රකාශය

මෙම ගැටලුවේදී අපට වලංගු වරහන් ලබා දී ඇත පේළියකි (vps) සමහර සංඛ්‍යා ඇති, සමහර ක්‍රියාකරුවන් (උදා +, -, *) සහ සමහර වරහන් (උදා: '(', ')').
වලංගු වරහන් නූල් (vps):

  1.  ""
  2. “D” යනු d යනු ඕනෑම සංඛ්‍යාවක් වේ
  3. A (වලංගු වරහන් වර්‍ගයක් නම් “(A)”
  4. “A * B” යනු කිසියම් ක්‍රියාකරුවෙකු නම් සහ A සහ ​​B වලංගු වරහන් වර්‍ග වේ.

අපගේ පරමාර්ථය දී ඇති නූලෙහි වරහන් වල උපරිම ගැඹුර සොයා ගැනීමයි.
e.g. “(1+(2*3)+((8)/4))+1”
අංක 8 හි උපරිම වරහන් වර්‍ග තුළ ඇති බවත් වරහන් වර්‍ගයේ ගැඹුර 3 ක් ඇති බවත් අපට දැකගත හැකිය.

වරහන් වර්‍ග ලීට්කෝඩ් විසඳුමේ උපරිම කැදැල්ල ගැඹුර
තවත් එක් උදාහරණයක් බලමු,
e.g. “1+(2*3)/(2-1)”
vps 2 * 3 හෝ වෙනත් vps 2-1, දෙකම වරහන් වල උපරිම ගැඹුර එනම් 1 වේ.

උදාහරණයක්

s = "(1+(2*3)+((8)/4))+1"
3

පැහැදිලි කිරීම:

අංක 8 යනු නූලෙහි කැදැලි වරහන් 3 ක් ඇතුලත ය.

s = "(1)+((2))+(((3)))"
3

ප්රවේශය

අපට ලබා දී ඇත්තේ නූල vps එකක් වන අතර වරහන් වල උපරිම ගැඹුර සොයාගත යුතුය. එබැවින්, අපට වරහන් වර්‍ග කෙරෙහි අවධානය යොමු කළ හැකි අතර අනෙක් අක්ෂර (අංක සහ ක්‍රියාකරුවන්) නොසලකා හැරිය හැකිය.

වරහන් වල ගැඹුර වැඩි වන්නේ නව කැදැලි වරහන් ආරම්භ වූ විට පමණි. එනම් ආරම්භක වරහන් '(' යන්නෙන් අදහස් වන්නේ වරහන් වල ගැඹුර 1 කින් වැඩි වන අතර වරහන් වර්‍ග වසා ඇති විට ගැඹුර 1 කින් අඩු වේ. එනම් ')' යන්නෙන් ගැඹුර 1 කින් අඩු වේ.

අපගේ ප්‍රවේශයේදී අපි භාවිතා කරන්නේ වත්මන් ගැඹුරේ විචල්‍යයක් (k ට ඉඩ දෙන්න) සහ උපරිම ගැඹුරේ විචල්‍යයක් (පිළිතුරට ඉඩ දෙන්න) .එය 0 ට ආරම්භ කර ඇත (ගැඹුර 0 යනු අප මුලින් සියලු වරහන් වලින් බැහැරව ඇත). ආදාන නූල වමේ සිට දකුණට ගමන් කිරීම ආරම්භ කරන්න. අප සාකච්ඡා කළ උපක්‍රමයට අනුව, අපට '(' ලකුණක් හමු වූ සෑම අවස්ථාවකම අපි වත්මන් ගැඹුර k 1 කින් වැඩි කරන්නෙමු. තවද අපට ') ලකුණක් හමු වූ විට අපි වත්මන් ගැඹුර k 1 කින් අඩු කරන්නෙමු.
වත්මන් ගැඹුර උපරිම ගැඹුරට වඩා වැඩි දැයි සෑම අවස්ථාවකම අපි පරීක්ෂා කරමු. ඔව් නම් අපි උපරිම ගැඹුර විචල්‍යයට වත්මන් ගැඹුර පවරන්නෙමු.
අවසාන වශයෙන් ගමන් කිරීමෙන් පසු, අපගේ පිළිතුරු විචල්‍යය උපරිම ගැඹුර ගබඩා කර ඇත, එබැවින් අපි එය ප්‍රතිදානය කරන්නෙමු.

ක්රියාත්මක කිරීම

වරහන් ලීට්කෝඩ් විසඳුමේ උපරිම කැදැල්ල ගැඹුර සඳහා සී ++ වැඩසටහන

#include <iostream>
using namespace std;

int maxDepth(string s) 
{
    int ans=0,k=0;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='(')k++;
        else if(s[i]==')')k--;
        ans=ans>k?ans:k;
    }
    return ans;
}
int main()
{
    cout<<maxDepth("(1)+((2))+(((3)))");
}
3

වරහන් ලීට්කෝඩ් විසඳුමේ උපරිම කැදැල්ල ගැඹුර සඳහා ජාවා වැඩසටහන

import java.util.*;
import java.lang.*;

class Solution
{  
    public static int maxDepth(String s) 
    {
        int ans=0,k=0;
        for(int i=0;i<s.length();i++)
        {
            if(s.charAt(i)=='(')k++;
            else if(s.charAt(i)==')')k--;
            ans=Math.max(ans,k);
        }
        return ans;
    }
    
    public static void main(String args[])
    {
        System.out.println(maxDepth("(1)+((2))+(((3)))"));
    }
}
3

වරහන් ලීට්කෝඩ් විසඳුමේ උපරිම කැදැල්ල ගැඹුර සඳහා සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

මත): දී ඇති ප්‍රකාශනය අපි වමේ සිට දකුණට ගමන් කරන්නෙමු. මේ අනුව එය O (n) වන අතර n යනු දී ඇති නූල් වල දිග වේ.

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (1): අපි නිරන්තර අමතර අවකාශ භාවිතා කර නැත. මේ අනුව අවකාශයේ සංකීර්ණතාව O (1) වේ.