สมมติว่าเรามีตัวเลขสองตัว n และ k เราต้องหาสตริงตัวพิมพ์เล็กที่เล็กที่สุดในพจนานุกรมของขนาด k และระยะทาง n ระยะทางเป็นผลรวมของจำนวนตัวอักษรในตัวอักษร ตัวอย่างเช่น 'a' มีตัวอักษรหมายเลข 1 'b' มี 2 'y' มี 25 'z' มี 26 เป็นต้น
ดังนั้น หากอินพุตเป็น n =15 k =3 เอาต์พุตจะเป็น "aam" เนื่องจาก "aam" เป็นสตริงที่เล็กที่สุดในพจนานุกรมของความยาว 3 ซึ่งเป็นระยะทาง 1 + 1 + 13 =15
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- dist :=อาร์เรย์ขนาด k และเติม 1
- เครดิต :=n - k
- i :=k - 1
- ในขณะที่เครดิต> 0 ทำ
- val :=ขั้นต่ำของเครดิตและ 25
- dist[i] :=dist[i] + วาล
- เครดิต :=เครดิต - val
- i :=i - 1
- เข้าร่วม (อักขระของ (d - 1 + ASCII ของ "a")) สำหรับแต่ละ d ใน dist) และส่งคืน
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(n, k):
dist = [1] * k
credit = n - k
i = k - 1
while credit > 0:
val = min(credit, 25)
dist[i] += val
credit -= val
i -= 1
return "".join(chr(d - 1 + ord("a")) for d in dist)
n = 15
k = 3
print(solve(n, k)) อินพุต
15, 3
ผลลัพธ์
aam
