Medium

题目描述

求解给定的方程并以字符串形式返回 ‘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’ 组成
  • 输入保证如果有唯一解，该解将是整数

解题思路

这是一个线性方程求解问题，可以转化为 ax + b = 0 的形式。

核心思路：

  1. 将方程按 ‘=’ 分为左右两边
  2. 解析每一边的项，分别计算 x 的系数和常数项
  3. 将右边的系数和常数移到左边，得到 left_coeff * x + left_const = 0
  4. 根据系数判断解的情况

解析过程：

  • 遍历每个字符，识别符号、数字和变量 x
  • 对于 “+3x”、"-2x"、“x”、“5” 等不同形式的项进行正确解析
  • 注意处理符号：方程右边的项移到左边时符号要取反

判断逻辑：

  • 如果 x 系数为 0 且常数项为 0：无限解
  • 如果 x 系数为 0 且常数项不为 0：无解
  • 如果 x 系数不为 0：唯一解 x = -常数项/系数

实现细节： 使用状态机方式解析字符串，正确处理数字的累积和符号的变化。

代码实现

class Solution {
public:
    string solveEquation(string equation) {
        int pos = equation.find('=');
        string left = equation.substr(0, pos);
        string right = equation.substr(pos + 1);
        
        auto parse = [](const string& s) -> pair<int, int> {
            int coeff = 0, const_val = 0;
            int i = 0, n = s.length();
            int sign = 1;
            
            while (i < n) {
                if (s[i] == '+') {
                    sign = 1;
                    i++;
                } else if (s[i] == '-') {
                    sign = -1;
                    i++;
                }
                
                if (i < n && s[i] == 'x') {
                    coeff += sign;
                    i++;
                } else {
                    int num = 0;
                    while (i < n && isdigit(s[i])) {
                        num = num * 10 + (s[i] - '0');
                        i++;
                    }
                    
                    if (i < n && s[i] == 'x') {
                        coeff += sign * num;
                        i++;
                    } else {
                        const_val += sign * num;
                    }
                }
            }
            return {coeff, const_val};
        };
        
        auto [left_coeff, left_const] = parse(left);
        auto [right_coeff, right_const] = parse(right);
        
        int final_coeff = left_coeff - right_coeff;
        int final_const = left_const - right_const;
        
        if (final_coeff == 0) {
            return final_const == 0 ? "Infinite solutions" : "No solution";
        }
        
        return "x=" + to_string(-final_const / final_coeff);
    }
};

class Solution:
    def solveEquation(self, equation: str) -> str:
        def parse(s):
            coeff = const = 0
            i = 0
            sign = 1
            
            while i < len(s):
                if s[i] == '+':
                    sign = 1
                    i += 1
                elif s[i] == '-':
                    sign = -1
                    i += 1
                
                if i < len(s) and s[i] == 'x':
                    coeff += sign
                    i += 1
                else:
                    num = 0
                    while i < len(s) and s[i].isdigit():
                        num = num * 10 + int(s[i])
                        i += 1
                    
                    if i < len(s) and s[i] == 'x':
                        coeff += sign * num
                        i += 1
                    else:
                        const += sign * num
            
            return coeff, const
        
        left, right = equation.split('=')
        left_coeff, left_const = parse(left)
        right_coeff, right_const = parse(right)
        
        final_coeff = left_coeff - right_coeff
        final_const = left_const - right_const
        
        if final_coeff == 0:
            return "Infinite solutions" if final_const == 0 else "No solution"
        
        return f"x={-final_const // final_coeff}"

public class Solution {
    public string SolveEquation(string equation) {
        string[] parts = equation.Split('=');
        string left = parts[0], right = parts[1];
        
        (int, int) Parse(string s) {
            int coeff = 0, constVal = 0;
            int i = 0, sign = 1;
            
            while (i < s.Length) {
                if (s[i] == '+') {
                    sign = 1;
                    i++;
                } else if (s[i] == '-') {
                    sign = -1;
                    i++;
                }
                
                if (i < s.Length && s[i] == 'x') {
                    coeff += sign;
                    i++;
                } else {
                    int num = 0;
                    while (i < s.Length && char.IsDigit(s[i])) {
                        num = num * 10 + (s[i] - '0');
                        i++;
                    }
                    
                    if (i < s.Length && s[i] == 'x') {
                        coeff += sign * num;
                        i++;
                    } else {
                        constVal += sign * num;
                    }
                }
            }
            return (coeff, constVal);
        }
        
        var (leftCoeff, leftConst) = Parse(left);
        var (rightCoeff, rightConst) = Parse(right);
        
        int finalCoeff = leftCoeff - rightCoeff;
        int finalConst = leftConst - rightConst;
        
        if (finalCoeff == 0) {
            return finalConst == 0 ? "Infinite solutions" : "No solution";
        }
        
        return $"x={-finalConst / finalCoeff}";
    }
}

var solveEquation = function(equation) {
    const [left, right] = equation.split('=');
    
    const parse = (expr) => {
        let xCoeff = 0;
        let constant = 0;
        let i = 0;
        let sign = 1;
        
        while (i < expr.length) {
            if (expr[i] === '+') {
                sign = 1;
                i++;
            } else if (expr[i] === '-') {
                sign = -1;
                i++;
            }
            
            let num = 0;
            let hasNum = false;
            
            while (i < expr.length && expr[i] >= '0' && expr[i] <= '9') {
                num = num * 10 + (expr[i] - '0');
                hasNum = true;
                i++;
            }
            
            if (i < expr.length && expr[i] === 'x') {
                if (!hasNum) num = 1;
                xCoeff += sign * num;
                i++;
            } else {
                if (hasNum) {
                    constant += sign * num;
                }
            }
        }
        
        return [xCoeff, constant];
    };
    
    const [leftX, leftConst] = parse(left);
    const [rightX, rightConst] = parse(right);
    
    const xCoeff = leftX - rightX;
    const constant = rightConst - leftConst;
    
    if (xCoeff === 0) {
        return constant === 0 ? "Infinite solutions" : "No solution";
    }
    
    return `x=${constant / xCoeff}`;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历整个方程字符串一次，其中 n 是方程长度
空间复杂度O(1)只使用常数个变量存储系数和常数项

相关题目