当前位置:网站首页>640. 求解方程 : 简单模拟题
640. 求解方程 : 简单模拟题
2022-08-10 14:31:00 【宫水三叶的刷题日记】
题目描述
这是 LeetCode 上的 640. 求解方程 ,难度为 中等。
Tag : 「模拟」、「数学」、「双指针」
求解一个给定的方程,将 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"
提示:
equation
只有一个'='
.equation
方程由整数组成,其绝对值在 范围内,不含前导零和变量'x'
。
模拟
为了方便,我们令 equation
为 s
。
由于运算符只有 +
和 -
,因此无须考虑运算优先级,可在遍历过程中进行计算。
使用变量 x
和 num
分别代指当前运算结果中 的系数以及数值部分,从前往后处理 s
的每个字符,根据字符类型进行分情况讨论,假设当前处理到的数值为 :
若 +/-
:此时影响的是下一个运算数值的正负,修改对应的op
标识;若 数值
:此时将完整的运算值进行取出(运算值可能是关于 的描述,可能是纯数值),假设连续段 之间为当前运算值,根据 是否为字符x
可知,是要将 的数值累加到变量x
,还是将 的数值累加到变量num
;若 =
:此时代表方程的左边已处理完,将变量x
和num
进行翻转(含义为将左边的运算结果移项到右边),并继续往后处理。
当整个字符串 s
处理完后,我们得到最终关于 的系数 x
,以及数值大小 num
。
根据 x
是否为 可知答案:
若 x
为 :此时根据num
是否为 可知是Infinite solutions
(对应num
为 ) 还是No solution
(对应num
不为 )若 x
不为 :对x
和num
进行约分后,返回对应答案。
Java 代码:
class Solution {
public String solveEquation(String s) {
int x = 0, num = 0, n = s.length();
char[] cs = s.toCharArray();
for (int i = 0, op = 1; i < n; ) {
if (cs[i] == '+') {
op = 1; i++;
} else if (cs[i] == '-') {
op = -1; i++;
} else if (cs[i] == '=') {
x *= -1; num *= -1; op = 1; i++;
} else {
int j = i;
while (j < n && cs[j] != '+' && cs[j] != '-' && cs[j] != '=') j++;
if (cs[j - 1] == 'x') x += (i < j - 1 ? Integer.parseInt(s.substring(i, j - 1)) : 1) * op;
else num += Integer.parseInt(s.substring(i, j)) * op;
i = j;
}
}
if (x == 0) return num == 0 ? "Infinite solutions" : "No solution";
else return "x=" + (num / -x);
}
}
TypeScript 代码:
function solveEquation(s: string): string {
let x = 0, num = 0, n = s.length
for (let i = 0, op = 1; i < n; ) {
if (s[i] == '+') {
op = 1; i++;
} else if (s[i] == '-') {
op = -1; i++
} else if (s[i] == '=') {
x *= -1; num *= -1; op = 1; i++;
} else {
let j = i
while (j < n && s[j] != '+' && s[j] != '-' && s[j] != '=') j++
if (s[j - 1] == 'x') x += (i < j - 1 ? Number(s.substring(i, j - 1)) : 1) * op
else num += Number(s.substring(i, j)) * op
i = j
}
}
if (x == 0) return num == 0 ? "Infinite solutions" : "No solution"
else return "x=" + (num / -x)
};
时间复杂度: 空间复杂度:使用 charAt
替换toCharArray
。复杂度为
最后
这是我们「刷穿 LeetCode」系列文章的第 No.640
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地
边栏推荐
猜你喜欢
随机推荐
In the second half of 2012 system architecture designers afternoon paper II
redhat替换yum源时redhat.repo无法删除或无法禁用的问题解决方法
公网IP和内网IP的区别[通俗易懂]
Parallels 将扩展桌面平台产品,以进一步改善在 Mac 上运行 Windows 的用户体验和工作效率
Vivado crashes or the message is not displayed
Steam教育在新时代中综合学习论
systemui状态栏添加新图标
BCG库简介
numpy.meshgrid()理解
2022年网络安全培训火了,缺口达95%,揭开网络安全岗位神秘面纱
C#实现访问OPC UA服务器
关于已拦截跨源请求CORS 头缺少 ‘Access-Control-Allow-Origin‘问题解决
司空见惯 - 股市狠狠下跌后,何時能反弹?
ICML 2022 | 基于随机注意力机制的可解释可泛化图学习
How is the monthly salary table stored in the database?Ask for a design idea
开源SPL消灭数以万计的数据库中间表
快速了解大端模式和小端模式
八大排序总是忘?快来这里~
兆骑科创创业赛事活动发布平台,创业赛事,项目路演
锂电池技术