資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：找出修復方程所需的更正次數
假設我們有一個字串 s，它表示一個形如 x+y=z 的方程。我們需要找到需要新增到 s 中的最小數字位數，以便該方程成立。
因此，如果輸入類似於 s = '2+6=7'，則輸出將為 2。
我們可以透過插入“1”和“2”將方程轉換為“21+6=27”。因此，所需的更正總數為 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，則
如果 carry 等於 0，則返回 0，否則返回 1
last1 := 如果 i >= 0，則 (A[i])，否則為 0
last2 := 如果 j >= 0，則 (B[j])，否則為 0
last3 := 如果 k >= 0，則 (C[k])，否則為 0
prefix1 := 如果 i >= 0，則 (A[從索引 0 到 i + 1])，否則為 0
prefix2 := 如果 j >= 0，則 (B[從索引 0 到 j + 1])，否則為 0
prefix3 := 如果 k >= 0，則 (C[從索引 0 到 k + 1])，否則為 0
如果 i <= -1 且 j <= -1，則
rhs := prefix3 - carry
如果 rhs <= 0，則
返回 |rhs|
如果 i 等於 -1 或 j 等於 -1，則
返回字串 rhs 的大小
否則，
返回 False
如果 k <= -1，則
返回 str(prefix1 + prefix2 + carry) 的大小
ans := 無限大
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(-1、i、j - 1、k - 1、carry2 的最大值) 的最小值
req := last3 - carry - last1
extra_zeros := 0 和 -1 - j 的最大值
如果 req < 0，則 carry2 := 1，否則為 0
ans = ans 和 1 + extra_zeros + dp(i - 1, -1 和 j 的最大值, k - 1, carry2) 的最小值
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
152 次瀏覽
