LeetCode 640 - Solve the Equation


https://leetcode.com/problems/solve-the-equation/#/description
Solve a given equation and return the value of x in the form of string "x=#value". The equation contains only '+', '-' operation, the variable x and its coefficient.
If there is no solution for the equation, return "No solution".
If there are infinite solutions for the equation, return "Infinite solutions".
If there is exactly one solution for the equation, we ensure that the value of x is an integer.
Example 1:
Input: "x+5-3+x=6+x-2"
Output: "x=2"
Example 2:
Input: "x=x"
Output: "Infinite solutions"
Example 3:
Input: "2x=x"
Output: "x=0"
Example 4:
Input: "2x+3x-6x=x+2"
Output: "x=-1"
Example 5:
Input: "x=x+2"
Output: "No solution"
http://www.cnblogs.com/grandyang/p/7350578.html
这道题给了我们一个用字符串表示的方程式,让我们求出x的解,根据例子可知,还包括x有无穷多个解和x没有解的情况。解一元一次方程没什么难度,难点在于处理字符串,如何将x的系数合并起来,将常数合并起来,化简成ax=b的形式来求解。博主最开始的思路是先找到等号,然后左右两部分分开处理。由于要化成ax=b的格式,所以左半部分对于x的系数都是加,右半部分对于x的系数都是减。同理,左半部分对于常数是减,右半部分对于常数是加。
那么我们就开始处理字符串了,我们定义一个符号变量sign,初始化为1,数字变量num,初始化为-1,后面会提到为啥不能初始化为0。我们遍历每一个字符,如果遇到了符号位,我们看num的值,如果num是-1的话,说明是初始值,没有更新过,我们将其赋值为0;反之,如果不是-1,说明num已经更新过了,我们乘上当前的正负符号值sign。这是为了区分"-3"和"3+3"这种两种情况,遇到-3种的符号时,我们还不需要加到b中,所以num此时必须为0,而遇到3+3中的加号时,此时num已经为3了,我们要把前面的3加到b中。
遇到数字的时候,我们还是要看num的值,如果是初始值,那么就将其赋值为0,然后计算数字的时候要先给num乘10,再加上当前的数字。这样做的原因是常数不一定都是个位数字,有可能是两位数或者三位数,这样做才能正确的读入数字。我们在遇到数字的时候并不更新a或者b,我们只在遇到符号位或者x的时候才更新。这样如果最后一位是数字的话就会产生问题,所以我们要在字符串的末尾加上一个+号,这样确保了末尾数字会被处理。
遇到x的时候比较tricky,因为可能是x, 0x, -x这几种情况,我们还是首先要看num的值是否为初始值-1,如果是的话,那么就可能是x或-x这种情况,我们此时将num赋值为sign;如果num不是-1,说明num已经被更新了,可能是0x, -3x等等,所以我们要将num赋值为num*sign。这里应该就明白了为啥不能将num初始化为0了,因为一旦初始化为0了,就没法区分x和0x这两种情况了。
那么我们算完了a和b,得到了ax=b的等式,下面的步骤就很简单了,只要分情况讨论得出正确的返回结果即可
https://www.cnblogs.com/seyjs/p/9660467.html
本题的思路就是解析字符串,然后是小学时候学的解方程的思想,以"2x+3x-6x+1=x+2",先把左右两边的x项和非x项进行合并,得到"-x+1=x+2",接下来就是移项,把x项移到左边,常数项移到右边,得到"2x=-1",最后的解就是x=-1/2。对于任意一个表达式ax+b = cx+d来说,最终都能得到解x=(d-b)/(a-c),这里要对(a-c)是否为0做判断,同时根据(d-b)是否为0等到Infinite solutions,No solution,常规解三种结果。

public String coeff(String x) {
    if (x.length() > 1 && x.charAt(x.length() - 2) >= '0' && x.charAt(x.length() - 2) <= '9')
      return x.replace("x", "");
    return x.replace("x", "1");
  }

  public String solveEquation(String equation) {
    String[] lr = equation.split("=");
    int lhs = 0, rhs = 0;
    for (String x : breakIt(lr[0])) {
      if (x.indexOf("x") >= 0) {
        lhs += Integer.parseInt(coeff(x));
      } else
        rhs -= Integer.parseInt(x);
    }
    for (String x : breakIt(lr[1])) {
      if (x.indexOf("x") >= 0)
        lhs -= Integer.parseInt(coeff(x));
      else
        rhs += Integer.parseInt(x);
    }
    if (lhs == 0) {
      if (rhs == 0)
        return "Infinite solutions";
      else
        return "No solution";
    }
    return "x=" + rhs / lhs;
  }

  public List<String> breakIt(String s) {
    List<String> res = new ArrayList<>();
    String r = "";
    for (int i = 0; i < s.length(); i++) {
      if (s.charAt(i) == '+' || s.charAt(i) == '-') {
        if (r.length() > 0)
          res.add(r);
        r = "" + s.charAt(i);
      } else
        r += s.charAt(i);
    }
    res.add(r);
    return res;

  }

X. Use regex
https://leetcode.com/articles/solve-the-equation/
  public String coeff(String x) {
    if (x.length() > 1 && x.charAt(x.length() - 2) >= '0' && x.charAt(x.length() - 2) <= '9')
      return x.replace("x", "");
    return x.replace("x", "1");
  }

  public String solveEquation(String equation) {
    String[] lr = equation.split("=");
    int lhs = 0, rhs = 0;
    for (String x : lr[0].split("(?=\\+)|(?=-)")) {
      if (x.indexOf("x") >= 0) {

        lhs += Integer.parseInt(coeff(x));
      } else
        rhs -= Integer.parseInt(x);
    }
    for (String x : lr[1].split("(?=\\+)|(?=-)")) {
      if (x.indexOf("x") >= 0)
        lhs -= Integer.parseInt(coeff(x));
      else
        rhs += Integer.parseInt(x);
    }
    if (lhs == 0) {
      if (rhs == 0)
        return "Infinite solutions";
      else
        return "No solution";
    } else
      return "x=" + rhs / lhs;

  }
https://blog.csdn.net/huanghanqian/article/details/77340481
还有大神巧妙地运用了regrex中的奇淫技巧。
比如:x +5 -2x = 6 -3x; 那么运用了 rex 之后,
左边的表达式 : tokens= { x, +5, -2x };  x的系数 = 1-2 =-1; 常数 = 5;
右边的表达式: tokens= { 6, -3x };  x的系数 = -3; 常数 = 6;

为啥 exp.split("(?=[-+])"); 得到的是包含+/-的token呢?可以看看stackoverflow的解答:https://stackoverflow.com/questions/10804732/what-is-the-difference-between-and-in-regex
?:  is for non capturing group
?=  is for positive look ahead
?!  is for negative look ahead
?<= is for positive look behind
?<! is for negative look behind
  • ?: Match expression but do not capture it.
  • ?= Match a suffix but exclude it from capture.
  • ?! Match if suffix is absent.
https://leetcode.com/problems/solve-the-equation/discuss/150021/Clear-Java-Code-with-Detailed-Example
e.g. x+5-3+x=6+x-2
  • Firstly, we split the equation by "=":
    leftPart is x+5-3+x;
    rightPart is 6+x-2;
  • Secondly, we sum up coefficient and the rest numbers separately, i.e.
    leftVals is 2x + 2, i.e., [2, 2];
    rightVals is x + 4, i.e., [1, 4];
  • Thirdly, we solve the simplified equation by moving all elements to the left of "=",
    cntX = leftVals[0] - rightVals[0];, i.e., 2 - 1 = 1,
    cntNum = leftVals[1] - rightVals[1];, i.e., 2 - 4 = -2,
    cntX * x + cntNum = 0, i.e., 1 * x + (-2) = 0,
    x = (-cntNum) / cntX, i.e., x = 2


Please note that
exp.split(""); split exp by 0-length string ("a+b-c" to "a", "+", "b", "-", "c")
exp.split("(?=[-+])");split exp by 0-length string only if they are follow by "-" or "+" ("a+b-c" to "a", "+b", "-c")
https://leetcode.com/problems/solve-the-equation/discuss/105311/Concise-Java-Solution
public String solveEquation(String equation) {
    int[] res = evaluateExpression(equation.split("=")[0]),  
     res2 = evaluateExpression(equation.split("=")[1]);
    res[0] -= res2[0];
    res[1] = res2[1] - res[1];
    if (res[0] == 0 && res[1] == 0) return "Infinite solutions";
    if (res[0] == 0) return "No solution";
    return "x=" + res[1]/res[0];
}  

public int[] evaluateExpression(String exp) {
    String[] tokens = exp.split("(?=[-+])"); 
    int[] res =  new int[2];
    for (String token : tokens) {
        if (token.equals("+x") || token.equals("x")) res[0] += 1;
 else if (token.equals("-x")) res[0] -= 1;
 else if (token.contains("x")) res[0] += Integer.parseInt(token.substring(0, token.indexOf("x")));
 else res[1] += Integer.parseInt(token);
    }
    return res;
}
https://leetcode.com/articles/solve-the-equation/
    public String coeff(String x) {
        if (x.length() > 1 && x.charAt(x.length() - 2) >= '0' && x.charAt(x.length() - 2) <= '9')
            return x.replace("x", "");
        return x.replace("x", "1");
    }
    public String solveEquation(String equation) {
        String[] lr = equation.split("=");
        int lhs = 0, rhs = 0;
        for (String x: lr[0].split("(?=\\+)|(?=-)")) {
            if (x.indexOf("x") >= 0) {

                lhs += Integer.parseInt(coeff(x));
            } else
                rhs -= Integer.parseInt(x);
        }
        for (String x: lr[1].split("(?=\\+)|(?=-)")) {
            if (x.indexOf("x") >= 0)
                lhs -= Integer.parseInt(coeff(x));
            else
                rhs += Integer.parseInt(x);
        }
        if (lhs == 0) {
            if (rhs == 0)
                return "Infinite solutions";
            else
                return "No solution";
        } else
            return "x=" + rhs / lhs;
    }
X.
https://leetcode.com/articles/solve-the-equation/
We treat the given equation as if we're bringing all the x's on the left hand side and all the rest of the numbers on the right hand side as done below for an example.
x+5-3+x=6+x-2
x+x-x=6-2-5+3
Thus, every x in the left hand side of the given equation is treated as positive, while that on the right hand side is treated as negative, in the current implementation. Likewise, every number on the left hand side is treated as negative, while that on the right hand side is treated as positive. Thus, by doing so, we obtain all the x's in the new lhs and all the numbers in the new rhs of the original equation.
Further, in case of an x, we also need to find its corresponding coefficients in order to evaluate the final effective coefficient of x on the left hand side. We also evaluate the final effective number on the right hand side as well.
Now, in case of a unique solution, the ratio of the effective rhs and lhs gives the required result. In case of infinite solutions, both the effective lhs and rhsturns out to be zero e.g. x+1=x+1. In case of no solution, the coefficient of x(lhs) turns out to be zero, but the effective number on the rhs is non-zero.
    public String coeff(String x) {
        if (x.length() > 1 && x.charAt(x.length() - 2) >= '0' && x.charAt(x.length() - 2) <= '9')
            return x.replace("x", "");
        return x.replace("x", "1");
    }
    public String solveEquation(String equation) {
        String[] lr = equation.split("=");
        int lhs = 0, rhs = 0;
        for (String x: breakIt(lr[0])) {
            if (x.indexOf("x") >= 0) {
                lhs += Integer.parseInt(coeff(x));
            } else
                rhs -= Integer.parseInt(x);
        }
        for (String x: breakIt(lr[1])) {
            if (x.indexOf("x") >= 0)
                lhs -= Integer.parseInt(coeff(x));
            else
                rhs += Integer.parseInt(x);
        }
        if (lhs == 0) {
            if (rhs == 0)
                return "Infinite solutions";
            else
                return "No solution";
        }
        return "x=" + rhs / lhs;
    }
    public List < String > breakIt(String s) {
        List < String > res = new ArrayList < > ();
        String r = "";
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '+' || s.charAt(i) == '-') {
                if (r.length() > 0)
                    res.add(r);
                r = "" + s.charAt(i);
            } else
                r += s.charAt(i);
        }
        res.add(r);
        return res;
    }
https://discuss.leetcode.com/topic/95207/easiest-java-solution-self-explanatory
    public String solveEquation(String equation) {
        if(equation == null || equation.length() == 0) {
     return equation;
 }

 String[] parts = equation.split("=");
 String left = parts[0];
 String right = parts[1];

 int[] lco = process(left);
 int[] rco = process(right);

 int x = lco[0] - rco[0];
 int co = rco[1] - lco[1];

 if(x == 0) {
     if(co == 0) {
         return "Infinite solutions";
            } else {
  return "No solution";
     }
 } else if(co == 0) {
     return "x=0";
 } else {
     return "x=" + "" + String.valueOf((int) (co/x));
 }
    }

    public int[] process(String left) {
        char[] array = left.toCharArray();
 int length = array.length;
 int prev = 1;
 int x = 0;
 int co = 0;
 int cur = 0;
 
 for(int i = 0; i < length; ++i) {
            if(array[i] != 'x') {
  if(array[i] == '-') {
      prev = -1;
  } else if(array[i] == '+') {
      prev = 1;
  } else {
      cur = 0;
             while(i < length && array[i] != '+' && array[i] != '-' && array[i] != 'x') {
          cur = cur * 10 + ((int)(array[i] - '0'));
   i++;
      }
      if(i < length && array[i] == 'x') {
          x = x + prev * ((int) (cur));
   i++;
      } else {
   co = co + prev * ((int) (cur));
      }
      --i;
      }
     } else {
         x += prev;
     }
        }
 return new int[]{x, co};
    }

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts