Etibarlı Mötərizələr etmək üçün Minimum Silin LeetCode Həll

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Bloomberg Facebook Goldman Sachs LinkedIn microsoft Salesforce Snapchat Über Yahoo
Qalaq SimBaxılıb 48

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

The Etibarlı Mötərizələr etmək üçün Minimum Silin LeetCode Həll - Sizə bir sim verilir s '(', ')' və kiçik ingilis hərflərindən ibarətdir.

Tapşırıq minimum sayda mötərizəni ( '(' və ya ')', istənilən mövqedən) çıxarmaqdır ki, nəticədə mötərizə sətri etibarlıdır və geri qaytarılır hər etibarlı sətir.

Formal olaraq, a mötərizə sətri Yalnız və yalnız aşağıdakı hallarda etibarlıdır:

  • Bu, yalnız kiçik hərflərdən ibarət boş sətirdir və ya
  • O, AB (B ilə birləşdirilən A) kimi yazıla bilər, burada A və B etibarlı sətirlərdir və ya
  • O, (A) kimi yazıla bilər, burada A etibarlı sətirdir.

Misal:Etibarlı Mötərizələr etmək üçün Minimum Silin LeetCode HəllPin

s = "lee(t(c)o)de)"
"lee(t(c)o)de"

Explanation:

Son bağlamanı silə bilərik sətri etibarlı etmək üçün mötərizə.

s = "))(("
""

Explanation:

Boş sətir də etibarlıdır.

Yanaşma:

Biz “count” adlı dəyişəni qoruyacağıq. Açılış mötərizəsinə rast gəlsək onu artıracağıq, bağlanan mötərizə ilə qarşılaşdıqda isə onu azaldacağıq. Nə vaxt "sayma" dəyəri mənfi olarsa, biz bunu qəbul edə bilmərik bağlama mötərizəsi, buna görə də onu siləcəyik.

Bundan sonra, onlara uyğun bağlama mötərizələri olmadığı üçün açılış mötərizələrinin "sayma" sayını sonundan çıxaracağıq.

Kodu

Etibarlı Mötərizələr C++ etmək üçün Minimum Silin Həll:

#include <bits/stdc++.h>
using namespace std;
string minRemoveToMakeValid(string s)
{
    string temp;
    int cnt = 0;
    for (auto ele : s)
    {
        if (ele == '(')
        {
            cnt++;
        }
        else if (ele == ')')
        {
            cnt--;
        }
        if (cnt < 0)
        {
            cnt++;
        }
        else
        {
            temp += ele;
        }
    }
    string answer;
    int n = temp.length();
    for (int i = n - 1; i >= 0; i--)
    {
        if (temp[i] != '(' or cnt <= 0)
        {
            answer += temp[i];
        }
        else
        {
            cnt--;
        }
    }
    reverse(answer.begin(), answer.end());
    return answer;
}
int main()
{
    string s = "lee(t(c)o)de)";
    cout << minRemoveToMakeValid(s) << endl;
    return 0;
}
"lee(t(c)o)de"

Etibarlı Mötərizələr Java Həlli etmək üçün Minimum Silin:

public class TutorialCup {
    public static String minRemoveToMakeValid(String s) {
        int n = s.length();
        StringBuilder temp = new StringBuilder();
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') {
                count++;
            } else if (s.charAt(i) == ')') {
                count--;
            }
            if (count < 0) {
                count++;
            } else {
                temp.append(s.charAt(i));
            }
        }
        n = temp.length();
        StringBuilder answer = new StringBuilder();
        for (int i = n - 1; i >= 0; i--) {
            if (temp.charAt(i) != '(' || count <= 0) {
                answer.append(temp.charAt(i));
            } else {
                count--;
            }
        }
        answer.reverse();
        return answer.toString();
    }

    public static void main(String[] args) {
        String s = "lee(t(c)o)de)";
        System.out.println(minRemoveToMakeValid(s));
    }
}
"lee(t(c)o)de"

Üçün Mürəkkəblik Təhlili Etibarlı Mötərizələr etmək üçün Minimum Silin LeetCode Həll:

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (n) çünki biz sətirdən cəmi iki dəfə keçirik, burada n giriş sətirinin uzunluğudur.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (n) çünki biz yeni sətir yaratmaqdan istifadə edirik.

Referans: https://en.wikipedia.org/wiki/Bracket_matching

Crack Sistemi Dizayn Müsahibələri
Translate »