Tạo thành số lớn nhất bằng cách sử dụng nhiều nhất một hoạt động hoán đổi C ++

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 tôi là tạo chương trình ứng dụng để tạo thành số lớn nhất 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ố lớn 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 = 63512
Output: 65312

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 số chữ số được hoán đổi này, số lớn 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 findLargestNumSwapDig(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 largest number created by swapping one digit is "<<findLargestNumSwapDig(num) << endl;
   return 0;
}

Đầu ra

The number is 792156
The largest number created by swapping one digit is972156

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à tìm ra sự hoán đổi góp phần tạo ra số lớn nhất có thể. Đối với điều này, chúng tôi sẽ quét số từ trái sang phải. Và sau đó hoán đổi các cặp đầu tiên tạo thành chữ số tiếp theo lớn hơn chữ số trước đó. Sự hoán đổi này sẽ dẫn đến số lượng lớn nhất.

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 findLargestNumSwapDig(int N){

   int currMaxDig = -1;
   int currMaxInd = -1;
   int lSwap = -1;
   int rSwap = -1;

   string strNum = to_string(N);
   for (int i = strNum.size() - 1; i >= 0; i--) {

      if (strNum[i] > currMaxDig) {
         currMaxDig = strNum[i];
         currMaxInd = i;
         continue;
      }
      if (strNum[i] < currMaxDig) {
         lSwap = i;
         rSwap = currMaxInd;
      }
   }
   if (lSwap == -1)
      return N;
   swap(strNum[lSwap], strNum[rSwap]);
   return stoi(strNum);
}
int main(){
   int num = 792156;
   cout<<"The number is "<<num<<endl;
   cout<<"The largest number created by swapping one digit is "<<findLargestNumSwapDig(num) << endl;
   return 0;
}

Đầu ra

The number is 792156
The largest number created by swapping one digit is972156