字符串等式处理

640.求解方程

难度中等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 <= 1000
  • equation 只有一个 '='.
  • 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)$

image-20220810110642683


640.求解方程
http://example.com/2022/08/10/leetcode每日一题/640.求解方程/
作者
madao33
发布于
August 10, 2022
许可协议