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函数呢？

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

• -2（来自-2或-2x）
• +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++

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