c++版 leetcode 241-一一网

【摘要】一、分治算法
Time：O（logn）8ms 解题思路（概述）—————————————————————————— 对于一个形如 x op y（op 为运算符，x 和 y 为数）的算式而言，它的结果组合取决于 x 和 y 的结果组合数，而 x 和 y 又可以写成形…

一、分治算法

Time：O（logn）8ms
解题思路（概述）——————————————————————————
对于一个形如 x op y（op 为运算符，x 和 y 为数）的算式而言，它的结果组合取决于 x 和 y 的结果组合数，而 x 和 y 又可以写成形如 x op y 的算式。

因此，该问题的子问题就是 x op y 中的 x 和 y：以运算符分隔的左右两侧算式解。

然后我们来进行分治算法三步走：

分解：按运算符分成左右两部分，分别求解
解决：实现一个递归函数，输入算式，返回算式解
合并：根据运算符合并左右两部分的解，得出最终解

解题思路（细节）——————————————————————————-
首先明确一点：不管多长的多项式运算，最后一步一定是两个明确数值的运算。
如 8*（4-7）-6*2 最后一步是（-24）-12，其中-24和6是明确的
再分解一下左边：上例中的得到 -24 ，也是同样有最后一步是两个明确的数值运算
8 * （-3），同样的右边是 6 * 2
再分解一下左边，容易得到结束点是：剩下一个数值或者两个（理论上也可以用一个统一解释）

完整的分解过程(宽度)：
输入:23-45（已转换）
第一步的分解：a:2和3-45；b:23和45；c:23-4和5；
第二部的细分：a部分：左边：直接返回2 右边：在分解，aa:3和45，ab:3-4和5
补充：同一个符号的左右各会产生至少一个，至多多个数值。左多个数和右多个数进行运算（两个循环搞定所有结果）如a:2和3-45 ，左边产生2，右边产生-5和-17，那么a这一级最终有-10，-34两个数值。

豪华注释版

class Solution {
public: vector<int> diffWaysToCompute(string expression) { // 创建两个容器，分别治理运算符两边的表达式 vector<int>vec1,vec2; // 创建一个容器存放每次表达式运算的结果(result) vector<int>res; // 记录当前表达式中的元素个数 int n=expression.size(); // 记录当前表达式的头元素是数字还是运算符 int falg=0; // 枚举表达式中的每一个元素 for(int i=0;i<n;i++){ // 若当前元素是运算符，则分治两边的表达式 if(expression[i]=='+' || expression[i]=='-' || expression[i]=='*'){ // 当前表达式的头元素是运算符 falg=1; //利用递归 治理左边 表达式：从0开始至第i个元素 vec1=diffWaysToCompute (string(expression,0,i)); // 同理 治理右边 vec2=diffWaysToCompute (string(expression,i+1,n-1-i)); // 枚举分治的俩容器，计算各个结果 for(int v1:vec1){ for(int v2:vec2){ if(expression[i]=='+'){ res.push_back(v1+v2); } if(expression[i]=='-'){ res.push_back(v1-v2); } if(expression[i]=='*'){ res.push_back(v1*v2); } } } } } // 当前表达式的头元素是数字，返回给所在的容器，return {}代表返回一个空容器 if(falg == 0)return{ // 将当前string形式的数字，强转成ACSII的数字 std::stoi(expression) }; // 当循环都结束是将存储的最终结果返回 return res; }
};

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46