leetcode 640. 求解方程
题目描述
求解一个给定的方程,将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 <= 1000
equation
只有一个'='
.equation
方程由整数组成,其绝对值在[0, 100]
范围内,不含前导零和变量'x'
。
题解——左右求值解方程
思路
其实对于所有的方程,不论是加减乘除括号都有,还是像这题的只有加减,我们都只要求出等号两边的值(其实是x的多项式),使其相等以解出未知数,就得到了答案。
对于求值的过程,类似于224.基本计算器和227.基本计算器II,区别就是遇到的数字可能是x的系数,要判定一下。
对于这题,由于只有加减,我们只要保存两边的x的系数和常数值,则结果就是(right_val-left_val)/(left_cnt/right_cnt)
具体实现过程:用一个sign
来记录符号(默认为正),一个flag
来记录当前是在左边还是右边,遍历一遍,如果发现+
,-
,改变sign
,如果发现=
,改变flag
和sign
,如果是数字,则截取一个完整的数字(注意:结束时,i
在数字后的位置),并判断此处是不是x
,如果是x
,存入cnt
,否则存入val
,并--i
以与for循环的++i
抵消,使进入循环时i
仍处于数字后的位置。结束后,用上面的式子解出x
,特判分母为零的情况。
代码看上去有点长,但实际上都是条件判断,难度不大;这题可以看做是基本计算器模板的应用,如果再引入了乘除、括号,也只要用同样的方法处理即可(栈、优先级列表……)。
代码
1 | class Solution { |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 HeRen's Blog!
评论