Mötərizələr əlavə etməyin müxtəlif yolları Leetcode həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon Bloomberg ByteDance Citadel Facebook Flipkart google microsoft Samsung Snapchat
Dinamik proqramlaşdırma Riyaziyyat Recursion SimBaxılıb 37

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 Mötərizələr əlavə etməyin müxtəlif yolları LeetCode Həlli – “Mötərizələr əlavə etməyin müxtəlif yolları” rəqəmlərin və operatorların sətir ifadəsi verildiyini bildirir. Nömrələri və operatorları qruplaşdırmaq üçün müxtəlif mümkün yolların hesablanmasından bütün mümkün nəticələri qaytarmalıyıq.

Cavabı istənilən qaydada qaytarın.

Misal:

Mötərizələr əlavə etməyin müxtəlif yolları Leetcode həlliPin

Input:  expression = "2-1-1"
Output: [0,2]

Explanation:

  • ((2-1)-1) = 0, mümkün nəticələrdən biridir.
  • (2-(1-1)) = 2, həm də mümkün nəticələrdən biridir.
Input:  expression = "2*3-4*5"
Output: [-34,-14,-10,-10,10]

Explanation:

  • (2*(3-(4*5))) = -34
  • ((2*3)-(4*5)) = -14
  • ((2*(3-4))*5) = -10
  • (2*((3-4)*5)) = -10
  • (((2*3)-4)*5) = 10
  • Deməli, [-34, -14, -10, -10, 10] mümkün nəticələrdir.

Yanaşma

Idea:

  1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir Recursion.
  2. Rekursiyanın hər addımında üzərində işləməli olduğumuz ifadənin sol və sağ ucları var.
  3. Hər bir i indeksi üçün təkrarlayın diapazon [l,r] və yenidən, [l,i-1] və [i+1,r] üçün rekurs  bir şərtlə ki, cari simvol operator olsun və qaytarılan cavablar toplusunu müvafiq olaraq adlandırılmış sol və sağ vektorda saxlayın.
  4. İndi, müvafiq olaraq sol və sağ vektorlarda qiymətləndirilən hər bir ifadə üçün nəticəni tətbiq etdikdən sonra bütün yeni dəyərləri tapın. a op b, burada a solda operand, b sağda operand və op operatordur.
  5. Cari vəziyyət üçün cavabı qaytarın {l,r};
  6. Biz də istifadə edərək nəticəni yadda saxlaya bilərik dinamik proqramlaşdırma.

Kodu

Mötərizələr əlavə etməyin müxtəlif yolları Leetcode C++ Həlli:

class Solution {
public:
    map<pair<int,int>,vector<int>> dp;
    vector<int> solve(int l,int r,string expression){
        if(dp.count({l,r})){
            return dp[{l,r}];
        }
        vector<int> ans;
        for(int i=l;i<=r;i++){
            if(expression[i]=='+' or expression[i]=='-' or expression[i]=='*'){
                vector<int> left = solve(l,i-1,expression);
                vector<int> right = solve(i+1,r,expression);
                
                for(auto& num1:left){
                    for(auto& num2:right){
                        if(expression[i]=='+'){
                            ans.push_back(num1+num2);
                        }
                        else if(expression[i]=='-'){
                            ans.push_back(num1-num2);
                        }
                        else{
                            ans.push_back(num1*num2);
                        }
                    }
                }
            }
        }
        if(ans.empty()){
            ans.push_back(stoi(expression.substr(l,r-l+1)));
        }
        return dp[{l,r}] = ans;
    }
    vector<int> diffWaysToCompute(string expression) {
        return solve(0,expression.length()-1,expression);
    }
};

Mötərizələr əlavə etməyin müxtəlif yolları Leetcode Java Həlli:

public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> ret = new LinkedList<Integer>();
        for (int i=0; i<input.length(); i++) {
            if (input.charAt(i) == '-' ||
                input.charAt(i) == '*' ||
                input.charAt(i) == '+' ) {
                String part1 = input.substring(0, i);
                String part2 = input.substring(i+1);
                List<Integer> part1Ret = diffWaysToCompute(part1);
                List<Integer> part2Ret = diffWaysToCompute(part2);
                for (Integer p1 :   part1Ret) {
                    for (Integer p2 :   part2Ret) {
                        int c = 0;
                        switch (input.charAt(i)) {
                            case '+': c = p1+p2;
                                break;
                            case '-': c = p1-p2;
                                break;
                            case '*': c = p1*p2;
                                break;
                        }
                        ret.add(c);
                    }
                }
            }
        }
        if (ret.size() == 0) {
            ret.add(Integer.valueOf(input));
        }
        return ret;
    }
}

Mötərizələr əlavə etməyin müxtəlif yolları üçün mürəkkəblik təhlili Leetcode həlli

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi Katalan nömrəsi. Hər bir vəziyyət üçün [l,r], biz [l,r] diapazonunda iterasiya edirik və onu iki dəstə [l,i-1] və [i+1,r] bölürük ki, bu da Katalan nömrəsinin hesablanmasına tərs bərabərdir. Beləliklə, zaman mürəkkəbliyi Katalan rəqəmləri ilə eynidir.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (cavab ölçüsü). 

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