给定一个表示非常大整数和整数k的数字的字符串num。
您最多可以交换整数的任意两个相邻数字k次。
以字符串形式返回您可以获得的最小整数。
范例1:
Input: num = "4321", k = 4
Output: "1342"
Explanation: The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.
Input: num = "36789", k = 1000
Output: "36789"
Explanation: We can keep the number without any swaps.
Example 4:
限制条件:1 <= num.length <= 30000
num contains digits only and doesn't have leading zeros.
1 <= k <= 10^9
这是代码class Solution {
public:
string minInteger(string num, int k) {
int n=num.length();
string min=num;
if (min.compare(num)>0)
min=num;
if (k<1)
return 0;
for (int i=0;i<n-1;i++){
for (int j=i+1;j<n;j++){
if (num[i]>num[j]){
swap(num[i],num[j]);
minInteger(num,k-1,min);
swap(num[i],num[j]);
}
}
}
return min;
}
};
我的输出,Input: num = "4321", k = 4
Output: "1234"
因此,基本上它返回的字符串是数字的升序,这是不希望的。我应该如何纠正呢?
最佳答案
问题陈述说,当您尝试交换代码中的任意两位数字时,只能交换相邻的数字。
而不是那两个循环,您应该只有一个试图在i
和i+1
位置交换数字的循环。
关于c++ - 在数字上最多进行K个相邻互换后的最小可能整数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62736878/