สมมติว่าเรามีสตริงที่เรียกว่า num ซึ่งแสดงถึงจำนวนเต็มที่มากและมีค่าอื่น k ด้วย เราสามารถสลับสองหลักใดๆ ของค่าที่อยู่ติดกันได้มากที่สุด k ครั้ง เราต้องหาค่าต่ำสุดที่เราหาได้
ดังนั้น หากอินพุตเท่ากับ num ="5432" k =4 เอาต์พุตจะเป็น 2453 เพราะหมายเลขแรกคือ 5432 จากนั้นหลังจากเฟสแรกจะเป็น 4532 จากนั้นจึงเท่ากับ 4523 ตามด้วย 4253 และในเฟสสุดท้าย 2453
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้
-
min_num :=จัดเรียงตัวเลขของ num
-
ผม :=0, to_find :=0
-
ในขณะที่ num ไม่เหมือนกับ min_num และ k> 0 และ i
-
indx :=ดัชนีของรายการ to_find จากดัชนี i เป็น num
-
ในขณะที่ indx ไม่เหมือนกับ -1 ให้ทำ
-
ถ้า indx - i <=k แล้ว
-
num :=num[จากดัชนี 0 ถึง i-1] ต่อ num[indx] concatenatenum[จากดัชนี i ถึง indx-1] ต่อ num[จากดัชนี indx+1 ถึงปลาย]
-
k :=k -(indx - i)
-
ผม :=ผม + 1
-
to_find :=0
-
indx :=ดัชนีของรายการ to_find จากดัชนี i เป็น num
-
-
มิฉะนั้น
-
ออกจากวง
-
-
-
to_find :=to_find + 1
-
-
ส่งคืนหมายเลข
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
def solve(num, k):
min_num = sorted(list(num))
min_num = ''.join(min_num)
i = 0
to_find = 0
while num != min_num and k > 0 and i < len(num):
indx = num.find(str(to_find), i)
while indx != -1:
if indx - i <= k:
num = num[:i] + num[indx] + num[i:indx] + num[indx+1:]
k -= (indx - i)
i += 1
to_find = 0
indx = num.find(str(to_find), i)
else:
break
to_find += 1
return num
num = "5432"
k = 4
print(solve(num, k)) อินพุต
"5432", 4
ผลลัพธ์
2453
