最近算法課在學習分治算法，在leetcode做了幾道easy和medium的題。運用分治算法的前提是：（1）把問題分成幾個同構的子問題（2）遞歸地解決每一個子問題（3）把各個子問題的答案結合起來構成原問題的答案。分治算法的復雜度分析可以通過大師定理。 個人感覺分治如果用得好，確實可以達到提高效率的作用。但如果處理得不夠妥當，有時會因為遞歸函數的層層嵌套，造成爆空間、超時等問題出現，得不償失。所以在寫代碼時一定要注意精簡，不要冗余，注意算法的復雜度！ 下面主要結合leetcode241題的求解過程進行分析。
原題：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”. ((2-1)-1) = 0 (2-(1-1)) = 2 Output: [0, 2]
Example 2 Input: “2*3-4*5” (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 Output: [-34, -14, -10, -10, 10]
思路：其實本題用分治的思路并不難想。從左至右遍歷字符串，遇到“+”“-”“*”的符號時，把符號左右兩邊分成兩個子字符串，再調用函數遞歸求解。
解法一：
#include<string>#include<vector>class Solution {public: vector<int> diffWaysToCompute(string input) { string s1,s2; vector<int> res; vector<int> res1,res2; s1.clear(); s2.clear(); res.clear(); res1.clear(); res2.clear(); if(!have_symbol(input)){ res.push_back(string_to_int(input)); return res; }else{ for(int i=0;i<input.length();i++){ s1=input.substr(0,i); s2=input.substr(i+1,input.length()-i-1); res1=diffWaysToCompute(s1); res2=diffWaysToCompute(s2); if(input[i]=='-'){ for(int m=0;m<res1.size();m++){ for(int n=0;n<res2.size();n++){ res.push_back(res1[m]-res2[n]); } } continue; } if(input[i]=='+'){ for(int m=0;m<res1.size();m++){ for(int n=0;n<res2.size();n++){ res.push_back(res1[m]+res2[n]); } } continue; } if(input[i]=='*'){ for(int m=0;m<res1.size();m++){ for(int n=0;n<res2.size();n++){ res.push_back(res1[m]*res2[n]); } } continue; } } } return res; } bool have_symbol(string s){ for(int i=0;i<s.length();i++){ if((s[i]=='+')||(s[i]=='-')||(s[i]=='*')){ return true; } } return false; } int string_to_int(string s){ int now,PRe,res; res=0; for(int i=0;i<s.length();i++){ pre=res; now=s[i]-'0'; res=pre*10+now; } return res; }};剛開始的代碼寫得有點冗余，結果是： 24 / 25 test cases passed. Status: Time Limit Exceeded。
解法二： 經過仔細分析，解法一的冗余主要體現在： （1）bool have_symbol(string s)這個函數本來是為了判斷字符串里面是否是單純的數字；如果是只有數字沒有符號就返回false。其實在 vector diffWaysToCompute(string input)中，如果遍歷完字符串之后，用條件res.size()=0即可判斷字符串中不存在符號。如此一來，就省去了每一層的string都走一遍bool have_symbol(string s)函數，可明顯提高效率。 （2） vector diffWaysToCompute(string input)這個函數中，這四個語句： s1=input.substr(0,i);s2=input.substr(i+1,input.length()-i-1);res1=diffWaysToCompute(s1);res2=diffWaysToCompute(s2); 應該是在input[i]==’-‘或’+’或’*’時才跑，不然的話完全沒必要。
改進了這兩處之后，代碼簡潔了很多，也很順利3ms通過了所有樣例。
#include<string>#include<vector>class Solution {public: vector<int> diffWaysToCompute(string input) { string s1,s2; vector<int> res,res1,res2; s1.clear();s2.clear(); res.clear();res1.clear();res2.clear(); for(int i=0;i<input.length();i++){ if((input[i]=='-')||(input[i]=='+')||(input[i]=='*')){ s1=input.substr(0,i); s2=input.substr(i+1,input.length()-i-1); res1=diffWaysToCompute(s1); res2=diffWaysToCompute(s2); for(int m=0;m<res1.size();m++){ for(int n=0;n<res2.size();n++){ if(input[i]=='-'){ res.push_back(res1[m]-res2[n]); }else if(input[i]=='+'){ res.push_back(res1[m]+res2[n]); }else{ res.push_back(res1[m]*res2[n]); } } } } } if(res.size()==0){ res.push_back(string_to_int(input)); } return res; } int string_to_int(string s){ int now,pre,res; res=0; for(int i=0;i<s.length();i++){ pre=res; now=s[i]-'0'; res=pre*10+now; } return res; }};這個故事告訴我，我的代碼能力仍然很弱。 當然此題只是過了，還遠不是最佳解。顯然上述解法對子問題存在著重復計算的問題，如果能夠保存子問題的答案，效率肯定會更高，這是算法方面的問題。以后如果有時間，可以繼續進行改進。
新聞熱點
疑難解答
圖片精選
