用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