640.求解方程

【LetMeFly】640.求解方程：过几天就看不懂了的迷惑性代码，但是是详解

力扣题目链接：https://leetcode.cn/problems/solve-the-equation/

求解一个给定的方程，将x以字符串 "x=#value" 的形式返回。该方程仅包含 '+' ， '-' 操作，变量 x 和其对应系数。

如果方程没有解，请返回 "No solution" 。如果方程有无限解，则返回 “Infinite solutions” 。

如果方程中只有一个解，要保证返回值 'x' 是一个整数。

 

示例 1：

输入: equation = "x+5-3+x=6+x-2"
输出: "x=2"

示例 2:

输入: equation = "x=x"
输出: "Infinite solutions"

示例 3:

输入: equation = "2x=x"
输出: "x=0"

 

 

提示:

• 3 <= equation.length <= 1000
• equation 只有一个 '='.
• equation 方程由整数组成，其绝对值在 [0, 100] 范围内，不含前导零和变量 'x' 。 ​​​

方法一：模拟

自认为这道题代码写得太具有迷惑性了，推荐一波官解。如果不嫌弃，也可以看一看我的思路：

首先确定等号的位置，这样我们就可以得知左边的表达式和右边的表达式的范围了。

对于某个表达式，我们求出其中$x$的系数和常数分别为多少。

那么具体怎么求呢？

首先我们把表达式分割成一个一个的小单元“-2”、“+3”、“5”、“-x”、“-2x”、“x”、“3x”等，分割规则是：遇到下一个“加减号”或到表达式结尾。

对于某个“小单元”，可以手写一个atoi函数求出这个小单元的值/$x$的系数（如果最后一个字符是x就加到$x$的系数上，否则就加到常数上）（如果最后一个字符是x，那么调用atoi时就把长度减少一位，不把x这个字符传递给atoi函数）

那么怎么写atoi函数呢？

首先要讨论传递到这个函数中的字符串有哪几种情况：

• + ```+3```（来自```+3```或```+3x```）
  + ```5```（来自```5```或```5x```）
  + ```-```（来自```-x```）
  + ``` ```（来自```x```）
  
  只要我们能处理好上述$5$种情况，那么对于本题来说，就是一个完美的```atoi```函数。（不能使用自带的```atoi```，否则```+```、```-```、``` ```都将被处理为$0$）
  
  最后回到初始问题，我们知道了左边$x$的系数、左边的常数、右边$x$的系数、右边的常数，如果“左边$x$系数等于右边并且左边常数不等于右边”那么就“无解”($x + 1 = x + 2$)，如果“左边$x$系数等于右边并且左边并且左边常数等于右边”那么就“无数解”($x + 1 = x + 1$)，否则方程的解为$x=\frac{右边常数 - 左边常数}{左边x系数 - 右边x系数}$
  
  + 时间复杂度$O(n)$，其中$n$是字符串长度，每个字符最多遍历$3$次（判断等号位置、确定下一个加减号的位置、确定某个“小单元”的值）
  + 空间复杂度$O(1)$
  
  ### AC代码
  
  #### C++
  
  ```cpp
  class Solution {
  private:
      int getEqualLocation(string& s) {
          for (int i = 0; i < s.size(); i++) {
              if (s[i] == '=')
                  return i;
          }
          return -1;  // Fake Return
      }
  
      int __LetMeFly_atoi(string& s, int left, int length) {
          if (length == 0) {
              return 1;
          }
          if (length == 1 && s[left] == '-') {
              return -1;
          }
          if (length == 1 && s[left] == '+') {
              return 1;
          }
          int k = 1;
          if (s[left] == '+')
              left++, length--;
          else if (s[left] == '-')
              left++, length--, k = -1;
          int ans = 0;
          while (length--) {
              ans *= 10;
              ans += s[left++] - '0';
          }
          return ans * k;
      }
  
      pair<int, int> getXandConst(string& s, int l, int r) {  // get [l, r) 's x and const
          pair<int, int> ans;
          int lastLoc = l;
          for (int nowLoc = l; nowLoc <= r; nowLoc++) {
              if (nowLoc != l && (nowLoc == r || s[nowLoc] == '+' || s[nowLoc] == '-')) {
                  // (lastLoc, nowLoc)
                  (s[nowLoc - 1] == 'x' ? ans.first : ans.second) += __LetMeFly_atoi(s, lastLoc, (s[nowLoc - 1] == 'x' ? nowLoc - 1 : nowLoc) - lastLoc);
                  lastLoc = nowLoc;
              }
          }
          return ans;
      }
  public:
      string solveEquation(string& equation) {
          int locEqual = getEqualLocation(equation);
          auto [leftX, leftConst] = getXandConst(equation, 0, locEqual);
          auto [rightX, rightConst] = getXandConst(equation, locEqual + 1, equation.size());
          if (leftX == rightX) {
              return leftConst == rightConst ? "Infinite solutions" : "No solution";
          }
          return "x=" + to_string((rightConst - leftConst) / (leftX - rightX));
      }
  };

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126262898