Giả sử chúng ta có một chuỗi gọi là num đại diện cho một số nguyên rất lớn và cũng có một giá trị khác là k. Chúng ta có thể hoán đổi hai chữ số liền kề bất kỳ của các giá trị nhiều nhất k lần. Chúng tôi phải tìm giá trị tối thiểu mà chúng tôi có thể nhận được.
Vì vậy, nếu đầu vào giống như num ="5432" k =4, thì đầu ra sẽ là 2453 vì số đầu tiên là 5432. Sau đó, sau giai đoạn đầu sẽ là 4532, sau đó là 4523, sau đó là 4253 và ở giai đoạn cuối là 2453.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau
-
min_num:=sắp xếp các chữ số của num
-
i:=0, to_find:=0
-
trong khi num không giống min_num và k> 0 và i
-
indx:=chỉ mục của mục to_find từ chỉ mục i trong num
-
trong khi indx không giống -1, do
-
nếu indx - i <=k thì
-
num:=num [từ chỉ mục 0 đến i-1] nối num [indx] concatenatenum [từ chỉ mục i đến indx-1] nối num [từ chỉ mục indx + 1 đến cuối]
-
k:=k - (indx - i)
-
i:=i + 1
-
to_find:=0
-
indx:=chỉ mục của mục to_find từ chỉ mục i trong num
-
-
nếu không,
-
đi ra từ vòng lặp
-
-
-
to_find:=to_find + 1
-
-
trả về số
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn
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)) Đầu vào
"5432", 4
Đầu ra
2453