侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【字符串, 模拟】求解方程

GabrielxD
2022-08-10 / 0 评论 / 0 点赞 / 68 阅读 / 1,203 字 / 正在检测是否收录...

题目

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

解题

方法一:字符串 模拟

思路

模拟:把等式按 '=' 分开,然后把两边的式子分别处理成 ax+bax+b​ 的形式:

这里 aabb 表示系数(coef)和常数(cons)。解析式子(Formula)字符串时,首先创建一个变量表示符号(sign)初始化为 '+' ,这是为了防止第一项的符号为正号省略时符号变量不被初始化,然后创建一个数字(num)维护某一项中的数字。再在输入的字符串后面加一个符号('+'),这是为了让式子中最后一项不被忽略。

遍历字符串中每个字符:

  • 如果当前字符是数字(不是 '+''-''x'),那么直接把当前维护的整数 num 加上该位(乘以 10 再加上该字符表示的整数),然后记录该项有出现数字(has_num = true)。
  • 如果当前字符是 'x',说明该项是未知项,首先如果该项没有出现数字的话说明这一项是 "x" (1x1x),那么把 num 赋值为 1(这是为了区分 "0x=0" 这样的测试点),然后根据符号(sign)把 num 累加进系数或者从系数中减去。这一项就处理完了,把 num 重置为 0has_num 重置为 false
  • 如果当前字符是 '+''-',说明该项是常数项或者是之前已经处理完了的未知项(这种情况不用管,因为变量已经重置过了,不会干扰)。那么就根据符号(sign)把 num 累加进常数或者从常数中减去,然后把维护下一项的符号为当前字符,重置 numhas_num

处理完后我们会得到这样两个式子:left: Formula{coef=a, cons=b}right: Formula{coef=c, cons=d},写成我们熟悉的数学形式就是:ax+b=cx+dax+b=cx+d,这样就简单了,把两边移项变成 (ac)x=db(a-c)x=d-b (代码中分别为 coefcons)。那么如果 coefcons 都为零的话等式就是 0x=00x=0 无穷解返回 "Infinite solutions"。如果 coef 不为零,cons 为零的话等式就是 kx=0kx=0 无解返回 "No solution"。如果都不为零的话这个等式就可以正常计算:x=conscoefx=\frac{cons}{coef} 按照题目给定的格式返回就可以了。

这题的字符串处理类似 2022 RoboCom 世界机器人开发者大赛-本科组(省赛)- RC-u3 跑团机器人

代码

struct Formula {
    int coef = 0, cons = 0;

    Formula(string str) {
        str += "+";
        char sign = '+';
        bool has_num = false;
        int num = 0;
        for (char ch : str) {
            switch (ch) {
                case '+': case '-':
                    cons += (sign == '+' ? num : -num);
                    sign = ch;
                    num = 0;
                    has_num = false;
                    break;
                case 'x':
                    if (!has_num) num = 1;
                    coef += (sign == '+' ? num : -num);
                    num = 0;
                    has_num = false;
                    break;
                default:
                    num = num * 10 + ch - '0';
                    has_num = true;
            }
        }
    }
};

class Solution {
public:
    string solveEquation(string equation) {
        int split = equation.find('=');
        Formula left(equation.substr(0, split)), right(equation.substr(split + 1));
        int coef = left.coef - right.coef, cons = right.cons - left.cons;
        if (!coef && !cons) return "Infinite solutions";
        if (!coef) return "No solution";
        return "x=" + to_string(cons / coef);
    }
};
class Formula {
    public int coef = 0, cons = 0;

    public Formula(String str) {
        str += "+";
        char sign = '+';
        boolean hasNum = false;
        int num = 0;
        for (char ch : str.toCharArray()) {
            switch (ch) {
                case '+': case '-':
                    cons += (sign == '+' ? num : -num);
                    sign = ch;
                    num = 0;
                    hasNum = false;
                    break;
                case 'x':
                    if (!hasNum) num = 1;
                    coef += (sign == '+' ? num : -num);
                    num = 0;
                    hasNum = false;
                    break;
                default:
                    num = num * 10 + ch - '0';
                    hasNum = true;
            }
        }
    }
}

class Solution {
    public String solveEquation(String equation) {
        int split = equation.indexOf('=');
        Formula left = new Formula(equation.substring(0, split));
        Formula right = new Formula(equation.substring(split + 1));
        int coef = left.coef - right.coef, cons = right.cons - left.cons;
        if (coef == 0 && cons == 0) return "Infinite solutions";
        if (coef == 0) return "No solution";
        return "x=" + (cons / coef);
    }
}
0

评论区