โปรแกรมค้นหา kth ที่เล็กที่สุด n ความยาว lexicographically สตริงที่เล็กที่สุดใน python

สมมติว่าเรามีตัวเลข n และอีกค่าหนึ่งคือ k ตอนนี้ ให้เราพิจารณาสตริงที่มีเพียง "0", "1" และ "2" ที่ไม่มีอักขระซ้ำกัน เราต้องเลือกสตริงที่มีความยาว n และค้นหาสตริงที่เล็กที่สุดที่ kth เกี่ยวกับพจนานุกรม หากไม่มีสตริงที่ k ให้คืนค่าสตริงว่าง

ดังนั้น หากอินพุตเป็น n =4 k =2 เอาต์พุตจะเป็น "0120"

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

• กำหนดวิธีการแก้ปัญหา() ซึ่งจะใช้เวลา s, k และสุดท้าย
• ถ้า s เหมือนกับ 0 แล้ว
  • คืนค่าสตริงว่าง
• สำหรับแต่ละอักขระ c ใน "012" ทำ
  • ถ้า c เหมือนกับครั้งสุดท้าย แล้ว
    • ติดตามตอนต่อไป
  • ถ้า k <2^(s-1) แล้ว
    • คืนค่า c + แก้ (s - 1, k, c)
  • k :=k - 2^(s-1)
• คืนค่าสตริงว่าง
• จากการเรียกเมธอดหลัก Solve(n, k, Null)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

โค้ดตัวอย่าง

class Solution:
   def solve(self, s, k, last=None):
      if s == 0:
         return ""
         for c in "012":
            if c == last:
               continue
            if k < 2 ** (s - 1):
               return c + self.solve(s - 1, k, c)
            k -= 2 ** (s - 1)
         return ""

ob = Solution()
n = 4
k = 2
print(ob.solve(n, k))

อินพุต

4, 2

ผลลัพธ์

0120