LeetCode 每日一题(20220701)

LeetCode每日一题

241. 为运算表达式设计优先级

• 题目： 给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。

  示例1：
  输入：expression = "2-1-1"
  输出：[0,2]
  解释：
  ((2-1)-1) = 0 
  (2-(1-1)) = 2
  
  示例2：
  输入：expression = "2*3-4*5"
  输出：[-34,-14,-10,-10,10]
  解释：
  (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
  

​

• 解题思路：

  对于一个形如x op y的算式而言(op为操作数)，它的结果取决于x和y的结果组合数。接下来该问题的子问题就是x op y 中的x和y的全部组合。属于分治问题。

  接下来就是分治算法三步走：

  1. 分解：按运算符分为左右两部分，分别求解

  2. 解决：实现一个递归函数，输入算式，返回算式解

  3. 合并：根据运算符合并左右两部分的解，得出最终解

• 代码：

  public class Solution {
      public IList<int> DiffWaysToCompute(string expression) {
          IList<int> res = new List<int>();
  
          if(IsDigit(expression)){
              res.Add(int.Parse(expression));
              return res;
          }
          
          IList<int> left = new List<int>();
          IList<int> right = new List<int>();
  
          // 遍历字符串
          for(int i = 0; i < expression.Length; i++){
              if(expression[i] == '+' || expression[i] == '-' || expression[i] == '*'){
                  left = DiffWaysToCompute(expression.Substring(0, i));
                  right =  DiffWaysToCompute(expression.Substring(i + 1, expression.Length - i - 1));
                  foreach(int l in left){
                      foreach(int r in right){
                          if(expression[i] == '+'){
                              res.Add(l + r);
                          }
                          if(expression[i] == '-'){
                              res.Add(l - r);
                          }
                          if(expression[i] == '*'){
                              res.Add(l * r);
                          }
                      }
                  }
              }
          }
          
          return res;
      }
  
      private bool IsDigit(string str){
          if(string.IsNullOrEmpty(str)){
              return false;
          }
          
          ASCIIEncoding ascii = new ASCIIEncoding();
          byte[] bytestr = ascii.GetBytes(str);        
   
          foreach (byte c in bytestr)                   
          {
              if (c < 48 || c > 57)                          
              {
                  return false;                             
              }
          }
          return true;
      }
  }