640. 求解方程

题目描述：

求解一个给定的方程，将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的解。

最终计算后会得到等式两边的系数coefficient1、coefficient2，常量number1、number2，通过这四个值来计算x的解。

• coefficient1 == coefficient2 && number1 == number2时，方程无限解，返回"Infinite solutions"
• coefficient1 == coefficient2 && number1 != number2时，方程解，返回"No solution"
• coefficient1 == coefficient2时，(number2-number1)/(coefficient1-coefficient2)即为解

if coefficient1 == coefficient2 {
    if number1 == number2 {
        return "Infinite solutions"
    } else {
        return "No solution"
    }
}
return fmt.Sprintf("x=%v", (number2-number1)/(coefficient1-coefficient2))

那么，如何计算=两边的式子得到系数coefficient1、coefficient2和常量number1、number2呢？

首先，将字符串从=分割，得到两个字符串

splits := strings.Split(equation, "=")

然后分别统计系数与常量值，将-替换为+-，再通过+分割，就是数个带符号的元素了。统计每个元素的数值，分别累加到系数或常量即可。

cal := func(s string) (coefficient, number int) {
    temps := strings.Replace(s, "-", "+-", -1)
    ss := strings.Split(temps, "+")
    for index := range ss {
        if ss[index] == "" {
            continue
        }
        temp, sign, num, hasx, valid := ss[index], 1, 0, false, false
        for i := range temp {
            if temp[i] == '-' {
                sign = -1
                continue
            }
            if temp[i] == 'x' {
                hasx = true
                continue
            }
            valid = true
            num = num*10 + int(temp[i]-'0')
        }
        sum := sign
        if valid {
            sum *= num
        }
        if hasx {
            coefficient += sum
        } else {
            number += sum
        }
    }
    return
}

复杂度：

• 时间复杂度：O(n)
• 空间复杂度：O(k)

执行结果：

• 执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
• 内存消耗：1.8 MB, 在所有 Go 提交中击败了78.95%的用户