最大で1つのスワップ操作C++を使用して最大数を形成します

この問題では、正の整数が与えられます。私たちのタスクは、最大1つのスワップ操作を使用して最大数を形成するプログラムを作成することです。

既存の番号の数字を使用して新しい番号を作成します。

形成される最大の数字は、既存の数字から1桁だけ交換できます。

問題を理解するために例を見てみましょう

Input: n = 63512
Output: 65312

ソリューションアプローチ

この問題を解決する1つの方法は、指定された数字の数字のペアを交換することによって作成されたすべての数字を見つけることです。これらの交換されたすべての桁番号のうち、最大のものが返されます。このために、数値を文字列に変換して位置を入れ替えます。

例

ソリューションの動作を説明するプログラム

#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;
}

出力

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

別のアプローチ

この問題を解決するためのもう1つのアプローチは、可能な最大数に寄与するスワップを見つけることです。このために、番号を左から右にスキャンします。次に、次の桁が前の桁よりも大きい最初のペアを交換します。この交換により、最大数になります。

例

ソリューションの動作を説明するプログラム

#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;
}

出力

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