[LeetCode]Solve the Equation

题目描述:

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"

题目大意:

给定一元一次方程,求x的值

解题思路:

字符串处理

用'='将等式分为左右两半

分别求左右两侧x的系数和常数值,记为lx, lc, rx, rc

令x, c = lx - rx, rc - lc

若x != 0,则x = c / x

否则,若c != 0,说明方程无解

否则,说明有无数组解

Python代码:

class Solution(object):
    def solveEquation(self, equation):
        """
        :type equation: str
        :rtype: str
        """
        left, right = equation.split('=')
        lx, lc = self.solve(left)
        rx, rc = self.solve(right)
        x, c = lx - rx, rc - lc
        if x: return 'x=%d' % (c / x)
        elif c: return 'No solution'
        return 'Infinite solutions'
    
    def solve(self, expr):
        x = c = 0
        num, sig = '', 1
        for ch in expr + '#':
            if '0' <= ch <= '9':
                num += ch
            elif ch == 'x':
                x += int(num or '1') * sig
                num, sig = '', 1
            else:
                c += int(num or '0') * sig
                num, sig = '', 1
                if ch == '-': sig = -1
        return x, c

 

本文链接:http://bookshadow.com/weblog/2017/07/09/leetcode-solve-the-equation/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码