C++で最大K個のスワップを実行して可能な最大数を見つけます

この問題では、2つの整数値nとkが与えられます。私たちのタスクは、最大でK個のスワップを実行することによって可能な最大数を見つけることです。

問題の説明： ここでは、最大で数の最大k桁を交換した後に作成される数を計算する必要があります。

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

入力： n =538 k =1

出力： 835

説明：

8と5を交換します。

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

この問題を解決するには、数の桁をk回交換し、からの数が最大かどうかを確認する必要があります。

数値の最大桁を見つけて、最初のインデックスで要素を交換する必要があります。数字の最初のk個のインデックスについても同様です。

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

例

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

出力

The maximum number created after 3 swaps is 65321