Chương trình tìm chuỗi nhỏ nhất thứ k có chiều dài n nhỏ nhất trong python

Giả sử chúng ta có một số n và một giá trị khác k. Bây giờ chúng ta hãy xem xét một chuỗi chỉ chứa "0", "1" và "2" trong đó không có ký tự nào được lặp lại liên tiếp. Chúng ta phải chọn các chuỗi có độ dài n như vậy và tìm chuỗi nhỏ nhất về mặt từ vựng thứ k. Nếu không có chuỗi thứ k, hãy trả về chuỗi trống.

Vì vậy, nếu đầu vào là n =4 k =2, thì đầu ra sẽ là "0120".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• xác định một phương thức giải quyết () điều này sẽ nhận s, k và cuối cùng
• nếu s giống 0, thì
  • trả về chuỗi trống
• đối với mỗi ký tự c trong "012", hãy thực hiện
  • nếu c giống với cuối cùng, thì
    • chuyển sang lần lặp tiếp theo
  • nếu k <2 ^ (s-1), thì
    • trả về c + giải quyết (s - 1, k, c)
  • k:=k - 2 ^ (s-1)
• trả về chuỗi trống
• Từ phương thức chính, cuộc gọi giải quyết (n, k, Null)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Mã mẫu

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))

Đầu vào

4, 2

Đầu ra

0120