第二周：( LeetCode241 ) Different Ways to Add Parentheses（c++）

2019-11-06 08:09:04

字体：大中小

来源：转载

供稿：网友

最近算法课在学习分治算法，在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; }};

这个故事告诉我，我的代码能力仍然很弱。当然此题只是过了，还远不是最佳解。显然上述解法对子问题存在着重复计算的问题，如果能够保存子问题的答案，效率肯定会更高，这是算法方面的问题。以后如果有时间，可以继续进行改进。

上一篇：c++输出当前时间

下一篇：c++中将数字转化为字符串