โปรแกรมหาจำนวนหลักขั้นต่ำของตัวเลขที่ถูกลบใน Python

สมมติว่าเรามีตัวเลขสองหลัก s และ t เราต้องหาวิธีที่จะลบตัวเลขในสตริงเพื่อที่:1. สองสตริงเหมือนกัน 2. ผลรวมของหลักที่ถูกลบจะถูกย่อให้เล็กสุด ส่งคืนผลรวมที่ย่อเล็กสุด

ดังนั้น หากอินพุตเป็น s ="41272" t ="172" ผลลัพธ์จะเป็น 6 เนื่องจากเราสามารถลบ "4" และ "2" ออกจากสตริงแรกเพื่อให้ได้ "172"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน lcs() นี่จะใช้เวลา a, b, m, n

• table :=เมทริกซ์ขนาด 2 มิติ (n + 1) x (m + 1) และเติมด้วย 0

• สำหรับผมอยู่ในช่วง 1 ถึง m ทำ

  • สำหรับ j ในช่วง 1 ถึง n ทำ

    • ถ้า a[i - 1] เหมือนกับ b[j - 1] แล้ว

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

    • มิฉะนั้น

      • table[i, j] =สูงสุดของ table[i - 1, j] และ table[i, j - 1])

• ส่งคืนตาราง[m, n]

• จากวิธีหลักให้ทำดังนี้

• m :=ขนาดของ a, n :=ขนาดของ b

• ค :=0

• สำหรับฉันในช่วง 0 ถึง m ทำ

  • c :=c + ASCII ของ a[i] - 48

• สำหรับผมอยู่ในช่วง 0 ถึง n ทำ

  • c :=c + ASCII ของ b[i] - 48

• ผลลัพธ์ :=c - lcs(a, b, m, n)

• ส่งคืนผลลัพธ์

ตัวอย่าง (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