题目描述
求解一个给定的方程，将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' 组成。
解法
方法一：数学
将方程 $equation$ 按照等号 “=” 切分为左右两个式子，分别算出左右两个式子中 "x" 的系数 $x_i$，以及常数的值 $y_i$。
那么方程转换为等式 $x_1 \times x + y_1 = x_2 \times x + y_2$。
- 当 $x_1 = x_2$：若 $y_1 \neq y_2$，方程无解；若 $y_1=y_2$，方程有无限解。
- 当 $x_1 \neq x_2$：方程有唯一解 $x=\frac{y_2-y_1}{x_1-x_2}$。
相似题目：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | 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)}'
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 | class Solution {
public String solveEquation(String equation) {
String[] es = equation.split("=");
int[] a = f(es[0]), b = f(es[1]);
int x1 = a[0], y1 = a[1];
int x2 = b[0], y2 = b[1];
if (x1 == x2) {
return y1 == y2 ? "Infinite solutions" : "No solution";
}
return "x=" + (y2 - y1) / (x1 - x2);
}
private int[] f(String s) {
int x = 0, y = 0;
if (s.charAt(0) != '-') {
s = "+" + s;
}
int i = 0, n = s.length();
while (i < n) {
int sign = s.charAt(i) == '+' ? 1 : -1;
++i;
int j = i;
while (j < n && s.charAt(j) != '+' && s.charAt(j) != '-') {
++j;
}
String v = s.substring(i, j);
if (s.charAt(j - 1) == 'x') {
x += sign * (v.length() > 1 ? Integer.parseInt(v.substring(0, v.length() - 1)) : 1);
} else {
y += sign * Integer.parseInt(v);
}
i = j;
}
return new int[] {x, y};
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 | func solveEquation(equation string) string {
f := func(s string) []int {
x, y := 0, 0
if s[0] != '-' {
s = "+" + s
}
i, n := 0, len(s)
for i < n {
sign := 1
if s[i] == '-' {
sign = -1
}
i++
j := i
for j < n && s[j] != '+' && s[j] != '-' {
j++
}
v := s[i:j]
if s[j-1] == 'x' {
a := 1
if len(v) > 1 {
a, _ = strconv.Atoi(v[:len(v)-1])
}
x += sign * a
} else {
a, _ := strconv.Atoi(v)
y += sign * a
}
i = j
}
return []int{x, y}
}
es := strings.Split(equation, "=")
a, b := f(es[0]), f(es[1])
x1, y1 := a[0], a[1]
x2, y2 := b[0], b[1]
if x1 == x2 {
if y1 == y2 {
return "Infinite solutions"
} else {
return "No solution"
}
}
return fmt.Sprintf("x=%d", (y2-y1)/(x1-x2))
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55 | function solveEquation(equation: string): string {
const [left, right] = equation.split('=');
const createExpr = (s: string) => {
let x = 0;
let n = 0;
let i = 0;
let sym = 1;
let cur = 0;
let isX = false;
for (const c of s) {
if (c === '+' || c === '-') {
if (isX) {
if (i === 0 && cur === 0) {
cur = 1;
}
x += cur * sym;
} else {
n += cur * sym;
}
isX = false;
cur = 0;
i = 0;
if (c === '+') {
sym = 1;
} else {
sym = -1;
}
} else if (c === 'x') {
isX = true;
} else {
i++;
cur *= 10;
cur += Number(c);
}
}
if (isX) {
if (i === 0 && cur === 0) {
cur = 1;
}
x += cur * sym;
} else {
n += cur * sym;
}
return [x, n];
};
const lExpr = createExpr(left);
const rExpr = createExpr(right);
if (lExpr[0] === rExpr[0]) {
if (lExpr[1] !== rExpr[1]) {
return 'No solution';
}
return 'Infinite solutions';
}
return `x=${(lExpr[1] - rExpr[1]) / (rExpr[0] - lExpr[0])}`;
}
|