难度: 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 <= 1000equation 只有一个 '='. [0, 100] 范围内且无任何前导零的整数和变量 'x' 组成。运行时间: 23 ms
内存: 15.9 MB
class Solution:
def solveEquation(self, equation: str) -> str:
def f(s):
x = y = 0
if s[0] != '-':
s = '+' + s
i, n = 0, len(s)
while i < n:
sign = 1 if s[i] == '+' else -1
i += 1
j = i
while j < n and s[j] not in '+-':
j += 1
v = s[i:j]
if v[-1] == 'x':
x += sign * (int(v[:-1]) if len(v) > 1 else 1)
else:
y += sign * int(v)
i = j
return x, y
a, b = equation.split('=')
x1, y1 = f(a)
x2, y2 = f(b)
if x1 == x2:
return 'Infinite solutions' if y1 == y2 else 'No solution'
return f'x={(y2 - y1) // (x1 - x2)}'
该题解的思路是将方程按 '=' 符号拆分成左右两部分，然后分别处理每一部分。对于每一部分，从左到右遍历，记录 'x' 的系数之和以及常数项之和。最后对比左右两部分 'x' 的系数是否相等，如果相等，再判断常数项之和是否相等，相等则有无穷多解，不等则无解；如果 'x' 的系数不等，则可以求出唯一解。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def solveEquation(self, equation: str) -> str:
def f(s):
x = y = 0
if s[0] != '-':
s = '+' + s
i, n = 0, len(s)
while i < n:
sign = 1 if s[i] == '+' else -1 # 获取符号
i += 1
j = i
while j < n and s[j] not in '+-': # 获取当前数字或者变量
j += 1
v = s[i:j]
if v[-1] == 'x': # 变量 x
x += sign * (int(v[:-1]) if len(v) > 1 else 1) # 获取 x 的系数
else: # 数字
y += sign * int(v) # 计算数字之和
i = j
return x, y
a, b = equation.split('=')
x1, y1 = f(a) # 左半部分 x 的系数和数字之和
x2, y2 = f(b) # 右半部分 x 的系数和数字之和
if x1 == x2:
return 'Infinite solutions' if y1 == y2 else 'No solution'
return f'x={(y2 - y1) // (x1 - x2)}' # 计算 x 的值
在处理方程时，如果遇到单个的'x'或'+x'，这意味着x前没有具体数字表示其系数，因此默认此时x的系数为1。在代码中，这通过检查变量`v`是否以'x'结尾且长度为1或者变量`v`除去最后的'x'后为空（适用于'+x'和'-x'的情况）来判断。如果符合这些条件，就将系数设置为1（对应的正负号由之前的符号决定）。
在函数`f(s)`中，如果变量`v`的末尾是'x'，这表示`v`是一个表示x的系数的字符串。检查`v`的长度是为了处理不同情况下的输入格式，例如'2x'、'+3x'、'-x'或仅仅是'x'。如果`v`的长度大于1，那么除去末尾的'x'后，剩下的部分将被转换为整数，这个整数就是x的系数。如果`v`的长度为1（即只有'x'），或者去除'x'后为空（如'+x'或'-x'），则默认x的系数为1。
在处理字符串`s`时，首先加上一个'+'符号是为了简化接下来的处理逻辑。这样做可以确保每个数字或变量前都明确地有一个符号（不管是正号'+'还是负号'-'），这使得在遍历字符串时，可以统一地处理每个数字或变量前的符号，而不需要在字符串开头特殊处理缺失符号的情况。
当方程的左右两部分中x的系数相等时，这意味着所有x项在方程两边相互抵消，因此方程简化为一个常数等式。此时，如果左右两边的常数项也相等（即`y1 == y2`），则方程有无限多解，即任何x的值都满足方程，因此返回'Infinite solutions'。如果常数项不相等（即`y1 != y2`），则方程无解，因为没有x的值能满足这样的不等式，因此返回'No solution'。