用Python编写的查找修正方程所需纠正数字数量的程序

用Python编写的查找修正方程所需纠正数字数量的程序

假设我们有一个字符串s,它代表形如x+y=z的方程。我们必须找到需要添加到s中的最小数字数量,以使等式成立。

因此,如果输入为s=’2+6=7’,则输出将为2。

我们可以将方程转换为“21+6=27”通过插入“1”和“2”。因此,所需的总纠正数量为2。

要解决这个问题,我们将遵循以下步骤:

  • 将s根据“+”字符分成若干部分,将左边的部分放入A中,将右边的部分放入rest中

  • 将rest根据“=”字符分成若干部分,将左边的部分放入B中,将右边的部分放入C中

  • 返回dp(A的大小-1,B的大小-1,C的大小-1,0)

  • 定义一个函数dp()。这将需要i,j,k,carry

  • 如果i <= -1且j <= -1且k <= -1,则

    • 如果进位与0相同,则返回0,否则返回1
  • 如果i >= 0,则last1 :=(A[i]),否则为0

  • 如果j >= 0,则last2 :=(B[j]),否则为0

  • 如果k >= 0,则last3 :=(C[k]),否则为0

  • 如果i >= 0,则prefix1 :=(从索引0到i + 1的A);否则为0

  • 如果j >= 0,则prefix2 :=(从索引0到j + 1的B);否则为0

  • 如果k >= 0,则prefix3 :=(从索引0到k + 1的C);否则为0

  • 如果i <= -1且j <= -1,则

    • rhs :=prefix 3 – 进位

    • 如果rhs <= 0,则

      • 返回|rhs|
    • 如果i与-1相同或j与-1相同,则
      • 返回rhs字符串的大小
    • 否则,
      • 返回False
    • 如果k <= -1,则
      • 返回prefix1 + prefix2 + carry的字符串大小
    • ans := infinity

    • carry2,lhs :=将(carry + last1 + last2)除以10的商和余数返回

    • 如果lhs与last3相同,则

      • ans := dp(i-1,j-1,k-1,carry2)
    • req := last3 – carry – last2

    • extra_zeros :=最大值为0,-1-i

    • 如果req <0,则carry2 := 1,否则为0

    • ans := ans和1 + extra_zeros + dp(maximum of-1,i,j-1,k-1,carry2)的最小值

    • req := last3 – carry – last1

    • extra_zeros := maximum of 0,-1-j

    • 如果req <0,则carry2 := 1,否则为0

    • ans = ans和dp(i-1,max(-1,j),k-1,carry2)的1 + extra_zeros的最小值

    • carry2,lhs :=将(last1 + last2 + carry)除以10的商和余数返回

    • ans := ans和1 + dp(i-1,j-1,k,carry2)的最小值

    • 返回ans

  • 从主方法返回dp(A的大小-1,B的大小-1,C的大小-1,0)

例子

看看以下实现以更好地理解-

class Solution:
   def solve(self, s):
      A, rest = s.split("+")
      B, C = rest.split("=")
      def dp(i, j, k, carry):
         if i <= -1 and j <= -1 and k <= -1:
            return 0 if carry == 0 else 1
         last1 = int(A[i]) if i >= 0 else 0
         last2 = int(B[j]) if j >= 0 else 0
         last3 = int(C[k]) if k >= 0 else 0
         prefix1 = int(A[: i + 1]) if i >= 0 else 0
         prefix2 = int(B[: j + 1]) if j >= 0 else 0
         prefix3 = int(C[: k + 1]) if k >= 0 else 0
         if i <= -1 and j <= -1:
            rhs = prefix3 - carry
            if rhs <= 0:
               return abs(rhs)
            if i == -1 or j == -1:
               return len(str(rhs))
            else:
               assert False
         if k <= -1:
            return len(str(prefix1 + prefix2 + carry))
         ans = float("inf")
         carry2, lhs = divmod(carry + last1 + last2, 10)
         if lhs == last3:
            ans = dp(i - 1, j - 1, k - 1, carry2)
         req = last3 - carry - last2
         extra_zeros = max(0, -1 - i)
         carry2 = 1 if req < 0 else 0
         ans = min(ans, 1 + extra_zeros + dp(max(-1, i), j - 1, k - 1, carry2))
         req = last3 - carry - last1
         extra_zeros = max(0, -1 - j)
         carry2 = 1 if req < 0 else 0
         ans = min(ans, 1 + extra_zeros + dp(i - 1, max(-1, j), k - 1, carry2))
         carry2, lhs = divmod(last1 + last2 + carry, 10)
         ans = min(ans, 1 + dp(i - 1, j - 1, k, carry2))
         return ans
      return dp(len(A) - 1, len(B) - 1, len(C) - 1, 0)

ob = Solution()
print (ob.solve('2+6=7'))

输入

'2+6=7'

输出

2

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程