这周选了分而治之的题目，这道middle题用的也是这个方法，但是，这个算法还可以继续优化，就像斐波拉契数列一样优化，用空间换时间，把已经算出来的字符串的所有可能的答案保存起来，这样就保证了，不再会出现重复计算的冗余时间。 对于一个表达式 a - b, a与b均为表达式，计算a - b的结果 我们需要先知道a的结果与b的结果。对于知道加parentheses的题，只要对表达中的每一个运算符都做这样的操作并递归，就可以得出所有可能结果，希望下面的例子可以帮助理解
2 * 3 - 4 * 5 / | / (2) * (3 - 4 * 5) (2 * 3) - (4 * 5) (2 * 3 - 4) * (5) / /(3 - 4 ) * 5 3 - (4 * 5) / / 3 4#include <iostream>#include <vector>#include <string>using namespace std;class Solution {public: vector<int> diffWaysToCompute(string input) { int inputLength = input.length(); vector<int> res; for (int i = 0; i <inputLength; i++){ if(input[i] == '+' || input[i]=='-' ||input[i]=='*' ){ vector<int> l = diffWaysToCompute(input.substr(0,i)); vector<int> r = diffWaysToCompute(input.substr(i+1,inputLength-i-1)); for(vector<int>::size_type j = 0; j < l.size(); j++) for(vector<int>::size_type k = 0; k< r.size(); k++){ switch (input[i]){ case '+': res.push_back(l[j]+r[k]); break; case '-': res.push_back(l[j]-r[k]); break; case '*': res.push_back(l[j]*r[k]); break; } } } } if(!res.size())res.push_back(atoi(input.c_str())); return res; }};新闻热点
疑难解答
