Жақша парағының ұяшығының максималды тереңдігі шешімінің шешімі


Күрделілік дәрежесі оңай
Жиі кіреді Bloomberg
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 болатынын көреміз. Біз 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) және максималды тереңдіктің айнымалысын (ans болсын) қолданамыз, екеуі де 0-ге дейін инициалданады (0 тереңдігі бастапқыда барлық жақшадан шыққанымызды білдіреді). Кіріс жолын солдан оңға қарай өтуді бастаңыз. Біз қарастырған трюкке сәйкес, біз қашан '(' белгісімен кездестіреміз, қазіргі тереңдікті k-ге 1 арттырамыз, ал ')' белгісімен кездестірсек, онда ағымдағы тереңдікті 1-ге кемітеміз.
Әр уақытта біз ағымдағы тереңдіктің максималды тереңдіктен үлкен екенін тексереміз. Егер иә болса, онда біз тереңдікті максималды тереңдікке айналдырамыз.
Төмен өткеннен кейін, біздің айнымалы мәніміз максималды тереңдікті сақтады, сондықтан оны шығарамыз.

Іске асыру

Жақшаның парақ кодының шешімінің ұялау тереңдігі үшін C ++ бағдарламасы

#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

Жақша парағының ұяшығының тереңдігі үшін Java бағдарламасы

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): Біз берілген өрнекті солдан оңға қарай өтіп жатырмыз. Сонымен, ол O (n), мұндағы n - берілген жолдың ұзындығы.

Ғарыштың күрделілігі 

O (1): Біз тұрақты қосымша кеңістікті қолданған жоқпыз. Сонымен, ғарыштық күрделілік O (1) болады.