Giả sử chúng ta có một chuỗi s biểu diễn một phương trình có dạng x + y =z. Chúng ta phải tìm số chữ số nhỏ nhất mà chúng ta cần thêm vào s để phương trình trở thành đúng.
Vì vậy, nếu đầu vào là s ='2 + 6 =7', thì đầu ra sẽ là 2.
Chúng ta có thể biến phương trình thành "21 + 6 =27" bằng cách chèn "1" và "2". Vì vậy, tổng số lần chỉnh sửa được yêu cầu là 2.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
chia s thành các phần dựa trên ký tự "+", đặt phần bên trái thành A và phần bên phải thành phần còn lại
-
chia phần còn lại thành các phần dựa trên ký tự "=", đặt phần bên trái thành B và phần bên phải thành C
-
trả về dp (kích thước A - 1, kích thước B - 1, kích thước C - 1, 0)
-
Định nghĩa một hàm dp (). Điều này sẽ đưa tôi, j, k, mang theo
-
nếu tôi <=-1 và j <=-1 và k <=-1 thì
-
trả về 0 nếu carry giống 0 nếu không là 1
-
-
last1:=(A [i]) nếu i> =0 nếu không thì 0
-
last2:=(B [j]) nếu j> =0 nếu không thì 0
-
last3:=(C [k]) nếu k> =0 nếu không thì 0
-
prefix1:=(A [từ chỉ mục 0 đến i + 1]) nếu i> =0 nếu không thì 0
-
prefix2:=(B [từ chỉ mục 0 đến j + 1]) nếu j> =0 nếu không thì 0
-
tiền tố 3:=(C [từ chỉ số 0 đến k + 1]) nếu k> =0 nếu không thì 0
-
nếu tôi <=-1 và j <=-1, thì
-
rhs:=prefix3 - carry
-
nếu rhs <=0, thì
-
trả về | rhs |
-
-
nếu tôi giống -1 hoặc j giống -1, thì
-
trả về kích thước của chuỗi rhs
-
-
nếu không,
-
trả về Sai
-
-
nếu k <=-1, thì
-
kích thước trả về của str (prefix1 + prefix2 + carry)
-
-
ans:=infinity
-
carry2, lhs:=return thương số và phần còn lại chia (carry + last1 + last2) cho 10
-
nếu lhs giống như last3, thì
-
ans:=dp (i - 1, j - 1, k - 1, carry2)
-
-
req:=last3 - carry - last2
-
extra_zeros:=tối đa là 0, -1 - i
-
carry2:=1 nếu req <0 nếu không thì 0
-
ans:=tối thiểu ans, 1 + extra_zeros + dp (tối đa -1, i, j - 1, k - 1, carry2)
-
req:=last3 - carry - last1
-
extra_zeros:=tối đa là 0, -1 - j
-
carry2:=1 nếu req <0 nếu không thì 0
-
ans =tối thiểu của (ans, 1 + extra_zeros + dp (i - 1, max (-1, j), k - 1, carry2))
-
carry2, lhs:=return thương số và phần còn lại chia (last1 + last2 + carry) cho 10
-
ans:=tối thiểu ans, 1 + dp (i - 1, j - 1, k, carry2)
-
trả lại ans
-
-
từ phương thức chính trả về dp (kích thước A - 1, kích thước B - 1, kích thước C - 1, 0)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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')) Đầu vào
'2+6=7'
Đầu ra
2