『LeetCode』640 求解方程

题目

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' 。

相似题目

分数加减运算 (中等)

题解

【求解方程】简单模拟

模拟

由于只有加减法，将方程化为 \(kx = b\) 的形式即可，结果为 \(x=\dfrac{b}{k}\)，剩下的工作就是解析字符串了。

可以根据 +-= 三个符号将等式划分，再分别计算 k 和 b 即可。

注意，如果是 \(0x=0\) 即 \(k, b\) 都为 0 时返回 "Infinite solutions"(无穷多解)，如果 \(0x=b(b \neq 0)\) 时返回 "No solution"(无解)

# Code language: Python
class Solution:
    def solveEquation(self, equation: str) -> str:
        # 化为 kx = b 的形式
        left, k, b, neg = 1, 0, 0, 1
        cur = ""
        for e in equation:
            if e == 'x':
                num = int(cur) if cur else 1
                k += left * neg * num
                cur = ""
            elif e in "+-=":
                if cur:
                    num = int(cur)
                    b += -left * neg * num
                if e == '=':
                    left = -1
                    neg = 1
                elif e == '-':
                    neg = -1
                else:
                    neg = 1
                cur = ""
            else:
                cur += e
        if cur:
            b += -left * neg * int(cur)
        if k == 0:
            return "Infinite solutions" if b == 0 else "No solution"
        return f"x={b // k}"

// Code language: Java
class Solution {
    public String solveEquation(String equation) {
        int left = 1, k = 0, b = 0, neg = 1;
        String cur = "";
        for (int i = 0, n = equation.length(); i < n; ++i) {
            char e = equation.charAt(i);
            if (e == 'x') {
                int num = cur.isEmpty() ? 1 : Integer.parseInt(cur);
                k += left * neg * num;
                cur = "";
            }
            else if (e == '+' || e == '-' || e == '=') {
                if (!cur.isEmpty()) {
                    int num = Integer.parseInt(cur);
                    b -= left * neg * num;
                }
                neg = 1;
                if (e == '=') left = -1;
                else if (e == '-') neg = -1;
                cur = "";
            }
            else cur += e;
        }
        if (!cur.isEmpty()) b -= left * neg * Integer.parseInt(cur);
        if (k == 0) return b == 0 ? "Infinite solutions" : "No solution";
        return "x=" + String.valueOf(b / k);
    }
}

// Code language: C++
class Solution {
public:
    string solveEquation(string equation) {
        int left = 1, k = 0, b = 0, neg = 1;
        string cur = "";
        for (char e: equation) {
            if (e == 'x') {
                int num = cur.empty() ? 1 : atoi(cur.c_str());
                k += left * neg * num;
                cur = "";
            }
            else if (e == '+' || e == '-' || e == '=') {
                if (!cur.empty()) {
                    int num = atoi(cur.c_str());
                    b -= left * neg * num;
                }
                neg = 1;
                if (e == '=') left = -1;
                else if (e == '-') neg = -1;
                cur = "";
            }
            else cur += e;
        }
        if (!cur.empty()) b -= left * neg * atoi(cur.c_str());
        if (k == 0) return b == 0 ? "Infinite solutions" : "No solution";
        return "x=" + to_string(b / k);
    }
};

时间复杂度: \(O(n)\)
空间复杂度: \(O(1)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』640 求解方程

题目

标签

相似题目

题解

模拟