โปรแกรมหาจำนวนไม่เกิน n โดยที่ตัวเลขทั้งหมดไม่ลดลงใน python

สมมติว่าเรามีตัวเลข n เราต้องหาจำนวนที่มากที่สุดให้น้อยกว่าหรือเท่ากับ n โดยที่ตัวเลขทั้งหมดไม่ลดลง

ดังนั้น หากอินพุตเท่ากับ n =221 เอาต์พุตจะเป็น 199

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

• หลัก :=รายการที่มีตัวเลขทั้งหมดเป็น n
• ถูกผูกไว้ :=null
• สำหรับ i ในขนาดช่วงของตัวเลข - 1 ลงเหลือ 0, ทำ
  • ถ้า digits[i]
  • ผูกพัน :=ฉัน
  • หลัก[i - 1] :=หลัก[i - 1] - 1
• ถ้าการผูกมัดไม่เป็นโมฆะ
  • สำหรับ i ในช่วงที่ผูกกับขนาดของหลัก ทำ
    • หลัก[i] :=9

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

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

class Solution:
   def solve(self, n):
      digits = [int(x) for x in str(n)]
      bound = None
      for i in range(len(digits) - 1, 0, -1):
         if digits[i] < digits[i - 1]:
            bound = i
            digits[i - 1] -= 1
         if bound:
            for i in range(bound, len(digits)):
               digits[i] = 9
         return int("".join(map(str, digits)))

ob = Solution()
n = 221
print(ob.solve(n))

อินพุต

221

ผลลัพธ์

199