Forskellige måder at tilføje parenteser Leetcode-løsning på

Systemdesign interviewspørgsmål kan være så åben, at det er for svært at kende den rigtige måde at forberede sig på. Nu er jeg i stand til at knække designrunderne fra Amazon, Microsoft og Adobe efter køb denne bog. Daglig revision af en design spørgsmål og jeg lover, at du kan knække designrunden.

Problemformulering

Forskellige måder at tilføje parenteser LeetCode Solution - "Different Ways to Add Parentheses" angiver, at givet et strengudtryk af tal og operatorer. Vi er nødt til at returnere alle mulige resultater fra beregning af alle forskellige mulige måder for at gruppere numre og operatorer.

Returner svaret i vilkårlig rækkefølge.

Eksempel:

Pin

Input:  expression = "2-1-1"

Output: [0,2]

Forklaring:

• ((2-1)-1) = 0, er et af de mulige resultater.
• (2-(1-1)) = 2, er også et af de mulige resultater.

Input:  expression = "2*3-4*5"

Output: [-34,-14,-10,-10,10]

Forklaring:

• (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
• Derfor er [-34, -14, -10, -10, 10] de mulige resultater.

Tilgang

Ide:

1. Hovedideen til at løse dette problem er at bruge rekursion.
2. Ved hvert trin af rekursionen har vi venstre og højre ende af udtrykket, som vi skal arbejde på.
3. Iterér for hvert indeks i i rækkevidde [l,r] og igen, gentagelse for [l,i-1] og [i+1,r]  forudsat at det aktuelle tegn er en operator, og gemmer det svar, der returneres i henholdsvis venstre og højre vektor.
4. Find nu alle nye værdier efter anvendelse af resultatet for hvert evalueret udtryk på henholdsvis venstre og højre vektor a op b, hvor a er en operand i venstre side, b er en operand i højre og op er operatoren.
5. Returner svaret for den aktuelle tilstand {l,r};
6. Vi kan også huske resultatet vha dynamisk programmering.

Kode

Forskellige måder at tilføje parenteser Leetcode C++ Løsning:

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);
    }
};

Forskellige måder at tilføje parenteser Leetcode Java Solution:

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;
    }
}

Kompleksitetsanalyse for forskellige måder at tilføje parenteser Leetcode-løsning på

Tidskompleksitet

Tidskompleksiteten af ​​ovenstående kode er catalansk nummer. For hver tilstand [l,r] itererer vi i området [l,r] og deler det i to sæt [l,i-1] og [i+1,r], som er omvendt lig med beregning af catalansk tal. Derfor er tidskompleksiteten den samme som for de catalanske tal.

Rumkompleksitet

Rumkompleksiteten af ​​ovenstående kode er O (svarstørrelse).