Trong bài toán này, chúng ta được cung cấp một số nguyên dương. Nhiệm vụ của chúng ta là tạo chương trình ứng dụng để tạo thành một số nhỏ hơn bằng cách sử dụng nhiều nhất một thao tác hoán đổi.
Chúng tôi sẽ tạo một số mới bằng cách sử dụng các chữ số của số hiện có. Số nhỏ nhất được tạo thành chỉ có thể có một chữ số được hoán đổi từ số hiện có.
Hãy lấy một ví dụ để hiểu vấn đề
Input: n = 63519 Output: 36519
Phương pháp tiếp cận giải pháp
Một phương pháp để giải quyết vấn đề là tìm tất cả các số được tạo ra bằng cách hoán đổi cặp chữ số của một số đã cho. Trong số tất cả các chữ số được hoán đổi này, số nhỏ nhất được trả về. Đối với điều này, chúng tôi sẽ chuyển đổi số thành chuỗi và hoán đổi vị trí.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include <iostream>
using namespace std;
int findSmallestNumSwapDig(int N){
string strNum = to_string(N);
string temp = strNum;
for (int i = 0; i < strNum.size(); i++) {
for (int j = i + 1; j < strNum.size(); j++) {
swap(strNum[i], strNum[j]);
if (stoi(strNum) < stoi(temp))
temp = strNum;
swap(strNum[i], strNum[j]);
}
}
return stoi(temp);
}
int main(){
int num = 792156;
cout<<"The number is "<<num<<endl;
cout<<"The smallest number created by swapping one digit is "<<findSmallestNumSwapDig(num) << endl;
return 0;
} Đầu ra
The number is 792156 The smallest number created by swapping one digit is192756
Một cách tiếp cận khác
Một cách tiếp cận khác để giải quyết vấn đề là sử dụng thêm một mảng bổ trợ aux []. Mảng này được sử dụng để lưu trữ chỉ số của chữ số nhỏ nhất ở bên phải (chỉ số lớn hơn) của chỉ số hiện tại, tức là aux [i] là chỉ số của chữ số nhỏ nhất ở bên phải chữ số của số đó. Khởi tạo aux [i] =-1, nếu không có chữ số nào như vậy tồn tại. Bây giờ, duyệt qua số từ chỉ số 0 đến n-1 và tìm số trong mảng aux [] nhỏ hơn giá trị hiện tại. Đối với giá trị chỉ số 0, hãy kiểm tra phần tử khác 0, nếu 0 xuất hiện, loại bỏ giá trị. Nếu tìm thấy bất kỳ phần tử nào, hãy hoán đổi arr [i] &arr [aux [i]] và trả lại số đã tạo.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include <bits/stdc++.h>
using namespace std;
int findSmallestNumSwapDig(int N){
string num = to_string(N);
int n = num.size();
int auxArr[n], right;
auxArr[n - 1] = -1;
right = n - 1;
for (int i = n - 2; i >= 1; i--) {
if (num[i] >= num[right])
auxArr[i] = right;
else {
if (num[i] == num[i + 1])
auxArr[i] = right;
else {
auxArr[i] = -1;
right = i;
}
}
}
int small = -1;
for (int i = 1; i < n; i++)
if (num[i] != '0') {
if (small == -1) {
if (num[i] < num[0])
small = i;
}
else if (num[i] <= num[small])
small = i;
}
if (small != -1)
swap(num[0], num[small]);
else {
for (int i = 1; i < n; i++) {
if (auxArr[i] != -1 && num[i] != num[auxArr[i]]) {
swap(num[i], num[auxArr[i]]);
break;
}
}
}
return stoi(num);
}
int main(){
int num = 792156;
cout<<"The number is "<<num<<endl;
cout<<"The smallest number created by swapping one digit is" <<findSmallestNumSwapDig(num)<< endl;
return 0;
} Đầu ra
The number is 792156 The smallest number created by swapping one digit is192756