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

更新於：2020年12月22日

瀏覽量：128

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告