Długość najdłuższego prawidłowego podłańcucha

Poziom trudności Ciężko
Często zadawane pytania Adobe Amazonka Apple Bloomberg ByteDance Cytadela eBay Facebook Google Microsoft wyrocznia Uber VMware Yahoo
sznurodwiedzajacy 418

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem Statement

W polu „Długość najdłuższego prawidłowego podłańcucha” podaliśmy ciąg który zawiera tylko nawiasy otwierające i zamykające. Napisz program, który znajdzie najdłuższy poprawny nawias podciąg.

Format wejściowy

Pierwsza i jedyna linia zawierająca ciąg znaków s.

Format wyjściowy

Pierwszy i jedyny wiersz zawierający liczbę całkowitą n oznaczającą długość najdłuższego prawidłowego podciągu nawiasu.

ograniczenia

  • 1 <= | s | <= 10 ^ 5
  • s [i] musi być „(” lub „)”

Przykład

(())())
6

Wyjaśnienie:  „(()) ()” To najdłuższy prawidłowy podciąg nawiasu w podanym powyżej ciągu. Więc nasza odpowiedź to 6.

Algorytm długości najdłuższego poprawnego podłańcucha

1. Utwórz pusty stos i wepchnij do niego -1. -1 ma na celu podanie wielkości liter bazowych dla następnego poprawnego ciągu

2. utwórz zmienną „res” do przechowywania danych wyjściowych

3. Przeszukuj wszystkie znaki od początku do końca

        a. Jeśli znakiem jest „(”, wypchnij bieżący indeks na stos
        b. Jeszcze,

  • Zdejmij element ze stosu.
  • Jeśli stos nie jest pusty, znajdź długość bieżącego prawidłowego podciągu, biorąc różnicę między bieżącym indeksem a wierzchołkiem stosu. Sprawdź, czy bieżąca długość jest większa niż wynik, a następnie zaktualizuj wynik.
  • Jeśli stos jest pusty, wypchnij bieżący indeks jako podstawę dla następnego prawidłowego podciągu.

4. Zwróć „res”

Implementacja algorytmu

s = „(())”
wepchnij -1 na stos i zainicjalizuj res = 0

i = 0, s [0] = '(', odłóż 0 na stos, teraz stos = [-1,0]
i = 1, s [1] = '(', odłóż 1 na stos, teraz stos = [-1,0,1]
dla i = 2, s [2] = ')', pop (), więc teraz stack = [-1,0]
res = max (res, i - stack.top ()) = max (0, 2-0) = max (0,2) = 2
i = 3, s [3] = ')', pop (), więc teraz stack = [-1]
res = max (res, i - stack.top ()) = max (2, 3 - (- 1)) = max (2,4) = 4

Dlatego najdłuższa długość to = res = 4.

Realizacja

Program C ++ dla długości najdłuższego poprawnego podłańcucha

#include<bits/stdc++.h>
using namespace std;
 
int maxLength(string s)
{
    int n = s.length();
 
    // Create a stack and push -1 as initial index to it.
    stack<int> stck;
    stck.push(-1);
 
    // Initialize res
    int res = 0;
 
    // Traverse all characters of given string
    for (int i=0; i<n; i++)
    {
        // If opening bracket, push index of it
        if (s[i] == '(')
          stck.push(i);
 
        else // If closing bracket, i.e.,s[i] = ')'
        {
            // Pop the previous opening bracket's index
            stck.pop();
 
            // Check if this length formed with base of
            // current valid substring is more than max 
            // so far
            if (!stck.empty())
                res = max(res, i - stck.top());
 
            // If stack is empty. push current index as 
            // base for next valid substring (if any)
            else stck.push(i);
        }
    }
 
    return res;
}
 
int main()
{
    string s;
    cin>>s;
    cout<<maxLength(s)<<endl;
    return 0;
}

Program Java dla długości najdłuższego poprawnego podłańcucha

import static java.lang.Math.max;
import java.util.Scanner;
import java.util.Stack;
class sum
{
    public static int maxLength(String s)
    {
        int n = s.length();

        // Create a stack and push -1 as initial index to it.
        Stack<Integer> stck = new Stack<Integer>();
        stck.push(-1);
        // Initialize res
        int res = 0;
        // Traverse all characters of given string
        for (int i=0; i<n; i++)
        {
            // If opening bracket, push index of it
            if(s.charAt(i) == '(')
              stck.push(i);

            else // If closing bracket, i.e.,s[i] = ')'
            {
                // Pop the previous opening bracket's index
                stck.pop();

                // Check if this length formed with base of
                // current valid substring is more than max 
                // so far
                if(stck.size()>0)
                    res = max(res, i - (Integer) stck.peek());
                // If stack is empty. push current index as 
                // base for next valid substring (if any)
                else stck.push(i);
            }
        }
        return res;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        String s = sr.next();
        System.out.println(maxLength(s));
    }
}
(()())((
6

Analiza złożoności długości najdłuższego poprawnego podłańcucha

Złożoność czasowa

Na) gdzie n jest rozmiarem danego ciągu. Tutaj przechodzimy przez ciąg znak po znaku i wykonujemy pewne operacje w stałym czasie.

Złożoność przestrzeni

Na) ponieważ używamy stosu. Tutaj maksymalny rozmiar stosu będzie wynosił n.

Wywiady dotyczące projektowania systemu pękania
Translate »