【C/C++】640. 求解方程

---

题目链接：640. 求解方程

题目描述

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

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

题目保证，如果方程中只有一个解，则 'x' 的值是一个整数。

提示:

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

示例 1：

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

示例 2：

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

示例 3:

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

整理题意

题目给定一个字符串，表示一个含有 x 的方程式，规定这个方程式中只含有 '+' ， '-' 操作以及变量 x 和其对应系数。

让我们求解 x 的值，以字符串的形式返回答案 "x=#value"，例如："x=2"，如果方程没有解，请返回 "No solution" 。如果方程有无限解，则返回 "Infinite solutions" 。

解题思路分析

根据解方程的流程，我们首先需要找到同类项进行合并：

• 含有 x 的项；
• 常数项。

我们将同类型进行合并然后移项即可。

那么还需考虑方程无解的情况和方程有无限解的情况，方程无解的情况为 x 项系数为 0 且常数项不为零，如：0 = 2；那么无限解的情况为 x 项系数为 0 且常数项也为 0，此时无论 x 取何值都会得到 0 = 0 的结果，所以此时方程有无限解。

具体实现

1. 用 cox 记录 x 项的系数，coi 记录常数项；
2. 同时利用 isleft 记录当前是在等号左边还是右边，当在等式左边时默认为正号，在等式右边时为负号，这是因为我们默认将所有项移至等式左边进行计算。
3. 遍历字符串进行解析，分类讨论：
   • 判断当前项是含有 x 的项还是常数项；
   • 当遇到 = 号时改变 isleft 的符号；

期间需要注意当 x 项仅含有 x 时，此时系数为 1，同样的如果常数项为空，此时为 0；

1. 最后判断 x 项的系数和常数项进行返回：
   • 当 x 的系数为 0 时且常数不为 0 返回 No solution
   • 当 x 的系数为 0 时且常数也为 0 才返回 Infinite solutions
   • 否则将系数和常数移至等式右边进行计算后按照题目格式进行返回答案。

复杂度分析

• 时间复杂度：O(n)O(n)O(n)，其中 n 是字符串 equation 的长度。
• 空间复杂度：O(1)O(1)O(1)，仅需常数空间。

代码实现

class Solution {
public:
    string solveEquation(string equation) {
        // cox 记录 x 的系数，coi 记录常数
        int cox = 0, coi = 0;
        // isleft 记录当前是在等号左边还是右边
        int i = 0, isleft = 1, n = equation.length();
        // 遍历字符串进行解析
        while(i < n){
            string temp = "";
            // f 为符号
            int f = 1;
            if(equation[i] == '-'){
                f = -1;
                i++;
            }
            else if(equation[i] == '+') i++;
            // 读取当前整数
            while(isdigit(equation[i])) temp += equation[i++];
            if(equation[i] == 'x'){
                // 如果没有数字且当前为 x，那么系数为 1
                if(temp == "") temp = "1";
                cox += stoi(temp) * isleft * f;
                i++;
            }
            else{
                // 如果没有数字且当前不为x的系数，那么为 0
                if(temp == "") temp = "0";
                coi += stoi(temp) * isleft * f; 
            }
            // 如果遇到 = 号，改变 isleft 的符号
            if(equation[i] == '='){
                isleft = -1;
                i++;
            }
        }
        if(cox == 0){
            // 当 x 的系数为 0 时且常数不为 0 返回 No solution
            if(coi != 0) return "No solution";
            // 当 x 的系数为 0 时且常数也为 0 才返回 Infinite solutions
            else return "Infinite solutions";
        }
        // 否则将系数和常数移至等式右边
        else return "x=" + to_string(-coi / cox);
    }
};

总结

• 该题为常规的字符串解析题，在处理字符串的时候需要注意各种情况的分类讨论。
• 核心思想为将字符串解析后将同类项进行合并，然后将 x 项系数和常数移项至等式右边进行计算。
• 需要特别注意当 x 项仅含有 x 时，此时系数为 1。
• 测试结果：

结束语

读书可以改变一个人的气质和格局。读书多了，由书香气所孕育出的精神长相，是时间难以改变的。读书虽然不会立马帮你解决当下的难题，但那些你读过的书，终将增长你的智慧，提升你的格局，让你成为一个有温度、有深度的人。新的一天，加油！