حداکثر عمق تودرتویی محلول Leetcode پرانتز


سطح دشواری ساده
اغلب در بلومبرگ
رشته

بیان مسأله

در این مشکل ، یک پرانتز معتبر به ما داده می شود رشته (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 خروجی خواهیم داشت.

حداکثر عمق تودرتویی محلول Leetcode پرانتز
بیایید یک مثال دیگر ببینیم ،
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 کاهش می یابد.

در رویکرد ما فقط از یک متغیر عمق فعلی (let k) و یک متغیر عمق حداکثر (let ans) استفاده خواهیم کرد. هر دو مقدار 0 را مقداردهی اولیه می کنند (عمق 0 به این معنی است که در ابتدا از همه پرانتزها خارج شده ایم). و شروع به پیمایش رشته ورودی از چپ به راست کنید. با توجه به ترفندی که در مورد آن بحث کردیم ، هر زمان که با علامت '(' عمق k k را به 1 افزایش دهیم و هر زمان با علامت ') مواجه شویم ، عمق k را با 1 کاهش خواهیم داد.
هر بار بررسی خواهیم کرد که آیا عمق جریان بیشتر از حداکثر عمق است. اگر بله ، عمق جریان را به متغیر حداکثر عمق نسبت می دهیم.
سرانجام بعد از پیمایش ، متغیر ans ما حداکثر عمق را ذخیره کرده است ، بنابراین ما آن را خروجی خواهیم داد.

پیاده سازی

برنامه C ++ برای حداکثر عمق تودرتویی محلول Leetcode پرانتز

#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

تجزیه و تحلیل پیچیدگی برای حداکثر عمق تودرتو محلول Leetcode پرانتز

پیچیدگی زمان

بر): ما در حال عبور از عبارت داده شده از چپ به راست هستیم. بنابراین O (n) است که n طول رشته داده شده است.

پیچیدگی فضا 

O (1): ما از فضاهای اضافی ثابت استفاده نکرده ایم. بنابراین پیچیدگی فضا O (1) است.