Graphical LeetCode - 640. Solving Equations (Difficulty: Moderate)

一、题目

求解一个给定的方程,将 x 以字符串 "x=#value" 的形式返回.该方程仅包含 '+' , '-' 操作,变量 x 和其对应系数.

如果方程没有解,请返回 "No solution" .如果方程有无限解,则返回 “Infinite solutions” .

如果方程中只有一个解,要保证返回值 'x' 是一个整数.

二、示例

2.1> 示例 1：

【输入】 equation = "x+5-3+x=6+x-2"
【输出】 "x=2"

2.2> 示例 2:

【输入】 equation = "x=x"
【输出】 "Infinite solutions"

2.3> 示例 3:

【输入】 equation = "2x=x"
【输出】 "x=0"

提示:

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

三、解题思路

3.1> 思路1：

根据题目描述,equation只有一个“=”,So we can first pass the entire string of equations throughsplit("=")split it into two parts：left side equation string&right side equation string.Why split the whole equation by the equal sign?？其实有两个主要的原因,首先：We want to parse the equation string,then we can provide a general method of splitting equation strings,In this way, the equation strings on the left and right sides can be split by calling this method..下面我们以equation="x+5-3+x=6+x-2"为例：

split by equals“left side equation string”和“right side equation string”之后,我们就需要Analytic equation of the string了.Strings are generally composed of three types：首先,“加号”或“减号”;其次,x变量;最后,非xinteger number of.那么,when we analyze,就可以通过“加号”或者“减号”to separate operator and not operator.这里可以通过substring(...)和indexOf(...)method to get the substring.以字符串x+5-3+x为例,判断indexOf("-")或indexOf("+")的下标位置,取indexValues under the smallest as a split at the end,At the end of the splitindex=1,所以通过e.substring(0, 1)Obtain intercept string“x”.最后,我们的eis the remaining string after the interception.Continue to split according to the above logic,最终会将“x+5-3+x”拆分为：“x”,“+5”,“-3”,“+x”.具体操作如下所示：

At this time there is a need to pay attention to special situation,that is if the first one is negative,So let's deal with it specially,Because we are in the process of the operation of the above,是通过indexOf确定“加号”或“减号”的位置,And then the interception in front of the string,那么,如果我们通过indexOf("-")Available subscript for position0,Then the intercepted string is an empty string“”了.所以,我们要通过indexOf("-", 1)或者indexOf("+", 1)来进行判断,即：从下标为1的位置开始,instead of subscripting from0的位置开始判断.具体操作如下所示：

After we finish parsing the string equation,我们就把xVariables are placed to the left of the equals sign,将非xvariable to the right of the equals sign.那么,在运算过程中,如果xvariable on the right,then since it is going to be moved to the left,所以,Its positive becomes negative,And negative numbers become positive numbers.对于非xThe movement of variables will also follow this.Then after moving,我们会统计x的总和（xSum）以及非x数字的总和（sum）.那么当xSum等于0并且sum等于0的时候,方法返回“Infinite solutions”;否则,如果只有xSum等于0,那么则返回“No solution”;否则,返回 x= sum/xSum.具体操作如下所示：

四、代码实现

4.1> 实现1：

class Solution {
    int xSum = 0; // 所有x,are moved to the left of the equal sign for calculation
    int sum = 0; // 所有数字,are moved to the right of the equal sign for calculation
    
    public String solveEquation(String equation) {
        calculate(equation.split("=")[0], true);
        calculate(equation.split("=")[1], false);
        return (xSum == 0 && sum == 0) ? "Infinite solutions" : (xSum == 0 ? "No solution" : "x=" + sum/xSum);
    }

    public void calculate(String equation, boolean left) {
        while(true) {
            if (equation == null || equation.equals("")) break;
            // 防止第一个数是负数,将其当做减号,So start from the first comparison
            int minusIndex = equation.indexOf("-", 1) == -1 ? Integer.MAX_VALUE : equation.indexOf("-", 1); 
            int plusIndex = equation.indexOf("+", 1) == -1 ? Integer.MAX_VALUE : equation.indexOf("+", 1);
            int endIndex = (minusIndex == Integer.MAX_VALUE && plusIndex == Integer.MAX_VALUE) ? equation.length() : Math.min(minusIndex, plusIndex);

            String numStr = equation.substring(0, endIndex);
            if (numStr.contains("x")) {
                // 针对x或者nx的特殊处理
                int xnum = (numStr.equals("x") || numStr.equals("+x")) ? 1 : (numStr.equals("-x") ? -1: Integer.valueOf(numStr.replace("x", "")));
                xSum += left ? xnum : -xnum;
            } else { // 减法操作
                sum += left ? -Integer.valueOf(numStr) : Integer.valueOf(numStr);
            }

            equation = equation.substring(endIndex);
        }
    }
}

今天的文章内容就这些了：

写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享 .

更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」