LC 640. 求解方程

题目描述

这是 LeetCode 上的 640. 求解方程 ,难度为 中等

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

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

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

示例 1:

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

输出: "x=2"

示例 2:
1
2
3
输入: equation = "x=x"

输出: "Infinite solutions"

示例 3:
1
2
3
输入: equation = "2x=x"

输出: "x=0"

提示:

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

模拟

为了方便,我们令 equations

由于运算符只有 +-,因此无须考虑运算优先级,可在遍历过程中进行计算。

使用变量 xnum 分别代指当前运算结果中 $x$ 的系数以及数值部分,从前往后处理 s 的每个字符,根据字符类型进行分情况讨论,假设当前处理到的数值为 $s[i]$:

  • 若 $s[i] =$ +/-:此时影响的是下一个运算数值的正负,修改对应的 op 标识;
  • 若 $s[i] =$ 数值:此时将完整的运算值进行取出(运算值可能是关于 $x$ 的描述,可能是纯数值),假设连续段 $s[i:j - 1]$ 之间为当前运算值,根据 $s[j - 1]$ 是否为字符 x 可知,是要将 $s[i:j - 2]$ 的数值累加到变量 x,还是将 $s[i:j - 1]$ 的数值累加到变量 num
  • 若 $s[i] =$ =:此时代表方程的左边已处理完,将变量 xnum 进行翻转(含义为将左边的运算结果移项到右边),并继续往后处理。

当整个字符串 s 处理完后,我们得到最终关于 $x$ 的系数 x,以及数值大小 num

根据 x 是否为 $0$ 可知答案:

  • x 为 $0$:此时根据 num 是否为 $0$ 可知是 Infinite solutions(对应 num 为 $0$) 还是 No solution(对应 num 不为 $0$)
  • x 不为 $0$:对 xnum 进行约分后,返回对应答案。

Java 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public String solveEquation(String s) {
int x = 0, num = 0, n = s.length();
char[] cs = s.toCharArray();
for (int i = 0, op = 1; i < n; ) {
if (cs[i] == '+') {
op = 1; i++;
} else if (cs[i] == '-') {
op = -1; i++;
} else if (cs[i] == '=') {
x *= -1; num *= -1; op = 1; i++;
} else {
int j = i;
while (j < n && cs[j] != '+' && cs[j] != '-' && cs[j] != '=') j++;
if (cs[j - 1] == 'x') x += (i < j - 1 ? Integer.parseInt(s.substring(i, j - 1)) : 1) * op;
else num += Integer.parseInt(s.substring(i, j)) * op;
i = j;
}
}
if (x == 0) return num == 0 ? "Infinite solutions" : "No solution";
else return "x=" + (num / -x);
}
}

TypeScript 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function solveEquation(s: string): string {
let x = 0, num = 0, n = s.length
for (let i = 0, op = 1; i < n; ) {
if (s[i] == '+') {
op = 1; i++;
} else if (s[i] == '-') {
op = -1; i++
} else if (s[i] == '=') {
x *= -1; num *= -1; op = 1; i++;
} else {
let j = i
while (j < n && s[j] != '+' && s[j] != '-' && s[j] != '=') j++
if (s[j - 1] == 'x') x += (i < j - 1 ? Number(s.substring(i, j - 1)) : 1) * op
else num += Number(s.substring(i, j)) * op
i = j
}
}
if (x == 0) return num == 0 ? "Infinite solutions" : "No solution"
else return "x=" + (num / -x)
};

  • 时间复杂度:$O(n)$
  • 空间复杂度:使用 charAt 替换 toCharArray。复杂度为 $O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.640 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。