难度中等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)$