Python程序：在最多k次相邻交换数字后找到可能的最小整数

假设我们有一个名为num的字符串，表示一个非常大的整数，还有一个值k。我们可以交换该值中任何两个相邻的数字，最多交换k次。我们必须找到我们可以得到的最小值。

因此，如果输入类似于num = "5432" k = 4，则输出将为2453，因为一开始数字是5432。然后在第一阶段它将变为4532，然后4523，然后4253，最后阶段为2453。

为了解决这个问题，我们将遵循以下步骤

  • min_num := 对num的数字进行排序

  • i := 0，to_find := 0

  • 当num与min_num不同且k > 0且i < num的大小，执行以下操作

    • indx := 从num中索引i开始查找to_find的索引

    • 当indx与-1不同，执行以下操作

      • 如果indx - i <= k，则

        • num := num[从索引0到i-1]连接num[indx]连接num[从索引i到indx-1]连接num[从索引indx+1到结尾]

        • k := k -(indx - i)

        • i := i + 1

        • to_find := 0

        • indx := 从num中索引i开始查找to_find的索引

      • 否则，

        • 退出循环

    • to_find := to_find + 1

  • 返回num

示例

让我们看看以下实现以获得更好的理解

Open Compiler
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

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

2453

更新于: 2021年10月6日

140次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告