Python程序：查找删除数字的最小数字和

假设我们有两个数字字符串s和t，我们需要找到一种方法来删除字符串中的数字，以便：1. 两个字符串相同 2. 删除数字的总和最小化 最后返回最小化后的和。

因此，如果输入类似于s = "41272" t = "172"，则输出将为6，因为我们可以从第一个字符串中删除"4"和"2"以得到"172"。

为了解决这个问题，我们将遵循以下步骤：

• 定义一个函数lcs()。它将接收a，b，m，n作为参数。

• table := 一个大小为(n + 1) x (m + 1) 的二维矩阵，并用0填充。

• 对于i从1到m，执行：

  • 对于j从1到n，执行：

    • 如果a[i - 1]与b[j - 1]相同，则

      • table[i, j] := table[i - 1, j - 1] + 2 *(a[i - 1]的ASCII码 - 48)

    • 否则，

      • table[i, j] = table[i - 1, j]和table[i, j - 1]中的最大值。

• 返回table[m, n]

• 在主方法中执行以下操作：

• m := a的大小，n := b的大小

• c := 0

• 对于i从0到m，执行：

  • c := c + a[i]的ASCII码 - 48

• 对于i从0到n，执行：

  • c := c + b[i]的ASCII码 - 48

• result := c - lcs(a, b, m, n)

• 返回result

示例（Python）

让我们看看下面的实现以更好地理解：

 在线演示

class Solution:
   def lcs(self, a, b, m, n):
      table = [[0 for i in range(n + 1)] for j in range(m + 1)]
      for i in range(1, m + 1):
         for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
               table[i][j] = table[i - 1][j - 1] + 2 * (ord(a[i - 1]) - 48)
            else:
               table[i][j] = max(table[i - 1][j], table[i][j - 1])
      return table[m][n]
   def solve(self, a, b):
      m = len(a)
      n = len(b)
      c = 0
      for i in range(m):
         c += ord(a[i]) - 48
      for i in range(n):
         c += ord(b[i]) - 48
      result = c - self.lcs(a, b, m, n)
      return result
ob = Solution()
s = "41272"
t = "172"
print(ob.solve(s, t))

输入

"41272", "172"

输出

6

Arnab Chakraborty

更新于：2020年12月22日

浏览量：128

开启你的职业生涯

完成课程获得认证

开始学习