[LeetCode] 241. Different Ways to Add Parentheses 添加括號的不同方式

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1:

Input:

"2-1-1"

Output:

[0, 2]

Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2

Example 2:

Input: "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

這道題讓給了一個(gè)可能含有加減乘的表達(dá)式，讓我們在任意位置添加括號，求出所有可能表達(dá)式的不同值。這道題乍一看感覺還蠻難的，給人的感覺是既要在不同的位置上加括號，又要計(jì)算表達(dá)式的值，結(jié)果一看還是道 Medium 的題，直接尼克楊問號臉？！遇到了難題不要害怕，從最簡單的例子開始分析，慢慢的找規(guī)律，十有八九就會在分析的過程中靈光一現(xiàn)，找到了破題的方法。這道題貌似默認(rèn)輸入都必須是合法的，雖然題目中沒有明確的指出這一點(diǎn)，所以我們也就不必進(jìn)行 valid 驗(yàn)證了。先從最簡單的輸入開始，若 input 是空串，那就返回一個(gè)空數(shù)組。若 input 是一個(gè)數(shù)字的話，那么括號加與不加其實(shí)都沒啥區(qū)別，因?yàn)椴淮嬖谟?jì)算，但是需要將字符串轉(zhuǎn)為整型數(shù)，因?yàn)榉祷氐氖且粋€(gè)整型數(shù)組。當(dāng)然，input 是一個(gè)單獨(dú)的運(yùn)算符這種情況是不存在的，因?yàn)榍懊嬲f了這道題默認(rèn)輸入的合法的。下面來看若 input 是數(shù)字和運(yùn)算符的時(shí)候，比如 "1+1" 這種情況，那么加不加括號也沒有任何影響，因?yàn)橹挥幸粋€(gè)計(jì)算，結(jié)果一定是2。再復(fù)雜一點(diǎn)的話，比如題目中的例子1，input 是 "2-1-1" 時(shí)，就有兩種情況了，(2-1)-1 和 2-(1-1)，由于括號的不同，得到的結(jié)果也不同，但如果我們把括號里的東西當(dāng)作一個(gè)黑箱的話，那么其就變?yōu)?()-1  和 2-()，其最終的結(jié)果跟括號內(nèi)可能得到的值是息息相關(guān)的，那么再 general 一點(diǎn)，實(shí)際上就可以變成 () ? () 這種形式，兩個(gè)括號內(nèi)分別是各自的表達(dá)式，最終會分別計(jì)算得到兩個(gè)整型數(shù)組，中間的問號表示運(yùn)算符，可以是加，減，或乘。那么問題就變成了從兩個(gè)數(shù)組中任意選兩個(gè)數(shù)字進(jìn)行運(yùn)算，瞬間變成我們會做的題目了有木有？而這種左右兩個(gè)括號代表的黑盒子就交給遞歸去計(jì)算，像這種分成左右兩坨的 pattern 就是大名鼎鼎的分治法 Divide and Conquer 了，是必須要掌握的一個(gè)神器。類似的題目還有之前的那道 Unique Binary Search Trees II 用的方法一樣，用遞歸來解，劃分左右子樹，遞歸構(gòu)造。

好，繼續(xù)來說這道題，我們不用新建遞歸函數(shù)，就用其本身來遞歸就行，先建立一個(gè)結(jié)果 res 數(shù)組，然后遍歷 input 中的字符，根據(jù)上面的分析，我們希望在每個(gè)運(yùn)算符的地方，將 input 分成左右兩部分，從而扔到遞歸中去計(jì)算，從而可以得到兩個(gè)整型數(shù)組 left 和 right，分別表示作用兩部分各自添加不同的括號所能得到的所有不同的值，此時(shí)我們只要分別從兩個(gè)數(shù)組中取數(shù)字進(jìn)行當(dāng)前的運(yùn)算符計(jì)算，然后把結(jié)果存到 res 中即可。當(dāng)然，若最終結(jié)果 res 中還是空的，那么只有一種情況，input 本身就是一個(gè)數(shù)字，直接轉(zhuǎn)為整型存入結(jié)果 res 中即可，參見代碼如下：

解法一：

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> res;
        for (int i = 0; i < input.size(); ++i) {
            if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
                vector<int> left = diffWaysToCompute(input.substr(0, i));
                vector<int> right = diffWaysToCompute(input.substr(i + 1));
                for (int j = 0; j < left.size(); ++j) {
                    for (int k = 0; k < right.size(); ++k) {
                        if (input[i] == '+') res.push_back(left[j] + right[k]);
                        else if (input[i] == '-') res.push_back(left[j] - right[k]);
                        else res.push_back(left[j] * right[k]);
                    }
                }
            }
        }
        if (res.empty()) res.push_back(stoi(input));
        return res;
    }
};

我們也可以使用 HashMap 來保存已經(jīng)計(jì)算過的情況，這樣可以減少重復(fù)計(jì)算，從而提升運(yùn)算速度，以空間換時(shí)間，豈不美哉，參見代碼如下：

解法二：

class Solution {
public:
    unordered_map<string, vector<int>> memo;
    vector<int> diffWaysToCompute(string input) {
        if (memo.count(input)) return memo[input];
        vector<int> res;
        for (int i = 0; i < input.size(); ++i) {
            if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
                vector<int> left = diffWaysToCompute(input.substr(0, i));
                vector<int> right = diffWaysToCompute(input.substr(i + 1));
                for (int j = 0; j < left.size(); ++j) {
                    for (int k = 0; k < right.size(); ++k) {
                        if (input[i] == '+') res.push_back(left[j] + right[k]);
                        else if (input[i] == '-') res.push_back(left[j] - right[k]);
                        else res.push_back(left[j] * right[k]);
                    }
                }
            }
        }
        if (res.empty()) res.push_back(stoi(input));
        memo[input] = res;
        return res;
    }
};

當(dāng)然，這道題還可以用動態(tài)規(guī)劃 Dynamic Programming 來做，但明顯沒有分治法來的簡單，但是既然論壇里這么多陳獨(dú)秀同學(xué)，博主還是要給以足夠的尊重的。這里用一個(gè)三維數(shù)組 dp，其中 dp[i][j] 表示在第i個(gè)數(shù)字到第j個(gè)數(shù)字之間范圍內(nèi)的子串添加不同括號所能得到的不同值的整型數(shù)組，所以是個(gè)三位數(shù)組，需要注意的是我們需要對 input 字符串進(jìn)行預(yù)處理，將數(shù)字跟操作分開，加到一個(gè)字符串?dāng)?shù)組 ops 中，并統(tǒng)計(jì)數(shù)字的個(gè)數(shù) cnt，用這個(gè) cnt 來初始化 dp 數(shù)組的大小，并同時(shí)要把 dp[i][j] 的數(shù)組中都加上第i個(gè)數(shù)字，通過 ops[i*2] 取得，當(dāng)然還需要轉(zhuǎn)為整型數(shù)。既然 dp 是個(gè)三維數(shù)組，那么肯定要用3個(gè) for 循環(huán)來更新，這里采用的更新順序跟之前那道 Burst Balloons 是一樣的，都是從小區(qū)間往大區(qū)間更新，由于小區(qū)間之前更新過，所以我們將數(shù)字分為兩部分 [i, j] 和 [j, i+len]，然后分別取出各自的數(shù)組 dp[i][j] 和 dp[j][i+len]，把對應(yīng)的運(yùn)算符也取出來，現(xiàn)在又變成了兩個(gè)數(shù)組中任取兩個(gè)數(shù)字進(jìn)行運(yùn)算，又整兩個(gè) for 循環(huán)，所以總共整了5個(gè) for 循環(huán)嵌套，啊呀媽呀，看這整的，看不暈?zāi)闼阄逸?，參見代碼如下：

解法三：

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        if (input.empty()) return {};
        vector<string> ops;
        int n = input.size();
        for (int i = 0; i < n; ++i) {
            int j = i;
            while (j < n && isdigit(input[j])) ++j;
            ops.push_back(input.substr(i, j - i));
            if (j < n) ops.push_back(input.substr(j, 1));
            i = j;
        }
        int cnt = (ops.size() + 1) / 2;
        vector<vector<vector<int>>> dp(cnt, vector<vector<int>>(cnt, vector<int>()));
        for (int i = 0; i < cnt; ++i) dp[i][i].push_back(stoi(ops[i * 2]));
        for (int len = 0; len < cnt; ++len) {
            for (int i = 0; i < cnt - len; ++i) {
                for (int j = i; j < i + len; ++j) {
                    vector<int> left = dp[i][j], right = dp[j + 1][i + len];
                    string op = ops[j * 2 + 1];
                    for (int num1 : left) {
                        for (int num2 : right) {
                            if (op == "+") dp[i][i + len].push_back(num1 + num2);
                            else if (op == "-") dp[i][i + len].push_back(num1 - num2);
                            else dp[i][i + len].push_back(num1 * num2);
                        }
                    }
                }
            }
        }
        return dp[0][cnt - 1];
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(241.添加括號的不同方式)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)添加括號的不同方式內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論