关于后端:640-求解方程-简单模拟题

题目形容

这是 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"

提醒:

• $3 <= equation.length <= 1000$
• equation 只有一个 '='.
• equation 方程由整数组成，其绝对值在 $[0, 100]$ 范畴内，不含前导零和变量 'x'。

模仿

为了不便，咱们令 equation 为 s。

因为运算符只有 + 和 -，因而毋庸思考运算优先级，可在遍历过程中进行计算。

应用变量 x 和 num 别离代指以后运算后果中 $x$ 的系数以及数值局部，从前往后解决 s 的每个字符，依据字符类型进行分状况探讨，假如以后解决到的数值为 $s[i]$：

• 若 $s[i] =$ +/-：此时影响的是下一个运算数值的正负，批改对应的 op 标识；
• 若 $s[i] =$ 数值：此时将残缺的运算值进行取出（运算值可能是对于 $x$ 的形容，可能是纯数值），假如间断段 $s[i:j – 1]$ 之间为以后运算值，依据 $s[j – 1]$ 是否为字符 x 可知，是要将 $s[i:j – 2]$ 的数值累加到变量 x，还是将 $s[i:j – 1]$ 的数值累加到变量 num；
• 若 $s[i] =$ =：此时代表方程的右边已解决完，将变量 x 和 num 进行翻转（含意为将右边的运算后果移项到左边），并持续往后解决。

当整个字符串 s 解决完后，咱们失去最终对于 $x$ 的系数 x，以及数值大小 num。

依据 x 是否为 $0$ 可知答案：

• 若 x 为 $0$：此时依据 num 是否为 $0$ 可知是 Infinite solutions（对应 num 为 $0$）还是 No solution（对应 num 不为 $0$）
• 若 x 不为 $0$：对 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)
};

• 工夫复杂度：$O(n)$
• 空间复杂度：应用 charAt 替换 toCharArray。复杂度为 $O(1)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.640 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布