640. Solving Equations: Simple Simulation Problems

题目描述

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

Since the operator only + 和 -,Therefore, there is no need to consider the operation priority,Calculations can be performed during the traversal process.

使用变量 x 和 num Respectively refer to the current operation result The coefficients and numerical part of ,从前往后处理 s 的每个字符,Discuss on a case-by-case basis according to character type,Suppose the currently processed value is ：

• 若 +/-：At this time, it affects the positive or negative of the next operand value,修改对应的 op 标识;
• 若 数值：At this time, the complete operation value is fetched（The operand value may be about 的描述,May be purely numeric）,Assume continuous segments between is the current operation value,根据 是否为字符 x 可知,是要将 The value is accumulated to the variable x,还是将 The value is accumulated to the variable num;
• 若 =：This represents that the left side of the equation has been processed,将变量 x 和 num 进行翻转（The meaning is to move the result of the operation on the left to the right）,and continue processing.

when the entire string s 处理完后,We get finally about 的系数 x,and numerical size num.

根据 x 是否为 know the answer：

• 若 x 为 ：此时根据 num 是否为 可知是 Infinite solutions（对应 num 为 ） 还是 No solution（对应 num 不为 ）
• 若 x 不为 ：对 x 和 num After making an appointment,Return the corresponding answer.

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 原题链接和其他优选题解.

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地