难度中等124收藏分享切换为英文接收动态反馈
求解一个给定的方程，将x以字符串 "x=#value" 的形式返回。该方程仅包含 '+' ， '-' 操作，变量 x 和其对应系数。
如果方程没有解，请返回 "No solution" 。如果方程有无限解，则返回 “Infinite solutions” 。
题目保证，如果方程中只有一个解，则 ‘x’ 的值是一个整数。
示例 1：
1
2
| 输入: equation = "x+5-3+x=6+x-2"
输出: "x=2"
|
示例 2:
1
2
| 输入: equation = "x=x"
输出: "Infinite solutions"
|
示例 3:
1
2
| 输入: equation = "2x=x"
输出: "x=0"
|
提示:
3 <= equation.length <= 1000equation 只有一个 '='.equation 方程由整数组成，其绝对值在 [0, 100] 范围内，不含前导零和变量 'x' 。
题解
思路是将方程通过=划分为前项和后项，然后分别对前项和后项处理，为了统一的划分各个项，可以首先替换-为+-，然后根据+划分，之后遍历处理所有的项，分别得到系数值和其他值，然后按照等式的计算公式得到系数coef和值val，方程解的判断：
coef=1 && val==0 也就是x可以任意取值，即可满足方程要求，所以是无限解coef==0&&val!=0 x取任意值也无法满足方程要求，没有解
其他情况直接输出x=+解的字符串即可
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
| public class Solution {
public String solveEquation(String equation) {
String[] equations = equation.split("=");
int[] res1 = getCoefVal(equations[0]), res2= getCoefVal(equations[1]);
int val = res2[1] - res1[1], coef = res1[0] - res2[0];
if (coef == 0 && val == 0)
return "Infinite solutions";
else if (coef == 0 && val != 0)
return "No solution";
return "x=" + String.valueOf(val/coef);
}
public int[] getCoefVal(String equation) {
List<Integer> coef = new ArrayList<>(), val = new ArrayList<>();
String temp = equation.replaceAll("-", "+-");
String[] items = temp.split("\\+");
for (String item:items) {
if (item.length()==0)
continue;
if (item.contains("x")) {
if (item.length()==1) {
coef.add(1);
} else if (item.length()==2 && item.charAt(0)=='-') {
coef.add(-1);
} else {
coef.add(Integer.valueOf(item.substring(0, item.length()-1)));
}
}else{
val.add(Integer.parseInt(item));
}
}
int[] res = new int[2];
for (int co:coef)
res[0] += co;
for (int v:val)
res[1] += v;
return res;
}
}
|
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$
