假设我们有一个名为 num 的字符串表示一个非常大的整数,并且还有另一个值 k。我们最多可以交换值的任意两个相邻数字 k 次。我们必须找到我们能得到的最小值。
因此,如果输入类似于 num = "5432" k = 4,那么输出将是 2453,因为第一个数字是 5432。然后在第一阶段之后它将是 4532,然后是 4523,然后是 4253,最后是 2453。
让我们看下面的实现来更好地理解
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