Leetcode 640 Solve the Equation

发表于 |

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”

分析：

  1. 题目意思是求解一个只含加减法的方程，我们自然想到平常是如何去解方程的
    1. 把含x的项都移到左边，把常数项都移到右边
    2. 构成ax=b的形式，最后x = b/a
    3. 显然如果a=b=0，有无限解
    4. a=0,b!=0,无解
    5. 其他情况，唯一解
  2. 我们发现答案只和系数有关，那么我们就分别计算x的系数v和常数项c的大小
  3. 如何去计算呢，我们发现不管是常数项还是未知项都是处于+-号中间的，那么有最简单的思路，我直接将一对+-号中间的字符串取出来，判断其是不是以x结尾，若是，则前面的系数加到v上，反之则加到c上，只需要注意处理下边界情况即可（但是这种思路当你真去写的时候发现有点坑，因为测试样例稀奇古怪，有好多烦人的情况）
  4. 所以还是采用直接迭代的方式是最稳的(也有点麻烦，垃圾样例)，具体见代码

思路：

  1. 因为s包含’=’，所以我们应该对左右两边分别求系数，然后再进行分析
  2. 构建函数求一串字符串的x系数和常数项大小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution(object):
    def solveEquation(self, s):
        """
        :type equation: str
        :rtype: str
        """
        s1,s2 = s.split('=')
        def helper(a):
            const, varia = 0, 0
            i,flag = 0,1 #flag用于判断系数正负
            while i < len(a):
                rec = '' # 用来记录系数
                while i < len(a) and a[i] not in '+-':
                    if a[i] == 'x':
                        # 可能出现单一个'x'或'-x'的情况
                        varia += int(rec) * flag if rec else flag
                        rec = ''
                    else:
                        rec += a[i]
                    i += 1
                if rec: const += int(rec) * flag
                if i >= len(a): break
                # 因为上面的判断语句，这里a[i]只会是'+-'中的一种
                if a[i] == '+': flag = 1
                else: flag = -1
                i += 1
            return const, varia
        c1,v1 = helper(s1)
        c2,v2 = helper(s2)
        v = v1 - v2
        c = c2 - c1
        if v == c == 0: return "Infinite solutions"
        if v == 0 and c != 0: return "No solution"
        else:
            return "x=" + str(c//v)