Trong bài toán này, chúng ta được cho hai giá trị nguyên n và k. Nhiệm vụ của chúng ta là tìm Số tối đa có thể bằng cách thực hiện tối đa K hoán đổi.
Mô tả sự cố: Ở đây, chúng ta cần tính số lớn nhất và được tạo sau khi hoán đổi tối đa k chữ số của số.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào: n =538 k =1
Đầu ra: 835
Giải thích:
Chúng tôi sẽ hoán đổi 8 và 5.
Phương pháp tiếp cận giải pháp
Để giải quyết vấn đề, chúng ta cần hoán đổi các chữ số của số k lần và kiểm tra xem số từ có lớn nhất không.
Chúng ta cần tìm chữ số lớn nhất của số và sau đó hoán đổi phần tử ở chỉ số đầu tiên. Và tiếp tục như vậy đối với k chỉ mục đầu tiên của các số.
Chương trình minh họa hoạt động của giải pháp của chúng tôi
Ví dụ
#include <bits/stdc++.h>
using namespace std;
void calcMaxNumAfterSwap(string number, int k, string& maxString, int n){
if (k == 0)
return;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (number[i] < number[j]) {
swap(number[i], number[j]);
if (number.compare(maxString) > 0)
maxString = number;
calcMaxNumAfterSwap(number, k - 1, maxString, n);
swap(number[i], number[j]);
}
}
}
}
int main(){
string str = "15263";
int k = 3;
int size = str.length();
string maxString = str;
calcMaxNumAfterSwap(str, k, maxString, size);
cout<<"The maximum number created after "<<k<<" swaps is "<<maxString;
return 0;
} Đầu ra
The maximum number created after 3 swaps is 65321