题目链接: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 只有一个 ‘=’.
  • 方程由绝对值在 [0, 100] 范围内且无任何前导零的整数和变量 ‘x’ 组成。

题解:模拟

最不喜欢的模拟题。

使用变量x和num分别存储x的系数和数值,遍历equation每个字符,根据字符类型分情况讨论,假设当前遍历的字符为equation[i]:

  • $equation[i]==’+’ || equation[i]==’-‘$:影响下一个运算值的正负,修改对应的flag标识。
  • $equation[i]$为数值:需要找出完整的数值部分,假设$equation[i:j-1]$部分为数值部分,需要判断$equation[j-1]$是否为’x’字符,如果是’x’字符,则表示前面$equation[i:j-2]$是x的系数,否则$equation[i:j-1]$是数值部分
  • $equation[i]$为 =:表示等式左边已经处理完,随后处理等式右边,将x的系数和数值部分均翻转(即取反)

遍历完整个字符串后,判断x(字符x的系数部分)是否为0:

  • 如果x为0:
    • 如果num也为0,则:Infinite solutions
    • 否则:No solution
  • 如果x不为0,则数值部分 除以 x系数即可得唯一解。

C++代码

class Solution {
public:
    string solveEquation(string equation) {
        int n=equation.length();
        int x=0,num=0;
        for(int i=0,flag=1;i<n;){
            if(equation[i]=='+'){
                flag=1;i++;
            }else if(equation[i]=='-'){
                flag=-1;i++;
            }else if(equation[i]=='='){
                x*=-1;num*=-1;flag=1;i++;
            }else{
                int j=i;
                while(j<n && equation[j]!='-' && equation[j]!='+' && equation[j]!='=') j++;
                if(equation[j-1]=='x'){
                    if(i< j-1){
                        string str=equation.substr(i,j-i-1);
                        x+=atoi(str.c_str())*flag;
                    }
                    else x+=flag;
                }else{
                    string str=equation.substr(i,j-i);
                    num+=atoi(str.c_str())*flag;
                }
                i=j;
            }
        }
        // cout<<x<<"==="<<num<<endl;
        if(x==0 && num==0){
            return "Infinite solutions";
        }else if(x==0 && num!=0){
            return "No solution";
        }else{
            return "x="+to_string(-num/x);
        }
    }
};