Bilangan minimum pertukaran antara dua rentetan supaya satu rentetan lebih besar daripada yang lain

Dalam artikel ini, kita akan membincangkan masalah manipulasi rentetan yang menarik - "Bilangan minimum pertukaran yang diperlukan antara dua rentetan supaya satu rentetan lebih besar daripada yang lain". Kami akan memahami masalah, strategi terperinci untuk menyelesaikannya, melaksanakannya dalam C++, dan menjelaskan konsep dengan contoh yang berkaitan.

Memahami penyataan masalah

Memandangkan dua rentetan yang sama panjang, matlamat kami adalah untuk menentukan bilangan minimum pertukaran aksara yang diperlukan untuk menjadikan satu rentetan lebih besar daripada yang lain. Aksara ditukar antara dua rentetan, dengan setiap pertukaran melibatkan watak daripada kedua-dua rentetan. Rentetan dibandingkan secara leksikografi, di mana 'a'

Kaedah

Ideanya ialah menggunakan algoritma tamak. Kami bermula dari permulaan rentetan, dan untuk setiap kedudukan, jika aksara dalam rentetan pertama lebih kecil daripada aksara yang sepadan dalam rentetan kedua, kita menukarnya. Jika mereka sama, kami mencari aksara yang lebih besar dalam rentetan kedua untuk ditukar. Jika tiada watak seperti itu ditemui, kita terus ke kedudukan seterusnya. Kami mengulangi proses ini sehingga semua aksara dalam rentetan telah diproses.

Contoh

Mari laksanakan pendekatan ini dalam C++ -

#include<bits/stdc++.h>
using namespace std;

int minSwaps(string &s1, string &s2) {
   int swaps = 0;
   int n = s1.size();
   for(int i=0; i<n; i++) {
      if(s1[i] < s2[i]) {
         swap(s1[i], s2[i]);
         swaps++;
      }
      else if(s1[i] == s2[i]) {
         for(int j=i+1; j<n; j++) {
               if(s2[j] > s1[i]) {
                  swap(s1[i], s2[j]);
                  swaps++;
                  break;
               }
         }
      }
   }
   return (s1 > s2) ? swaps : -1;
}

int main() {
   string s1 = "bbca";
   string s2 = "abbc";
   int swaps = minSwaps(s1, s2);
   if(swaps != -1)
      cout << "Minimum swaps: " << swaps << "\n";
   else
      cout << "Cannot make string 1 greater\n";
   return 0;
}

Output

Minimum swaps: 2

Kes Ujian

Mari kita pertimbangkan rentetan "bbca" dan "abbc". Pertukaran berikut akan berlaku −

• Tukar 'b' dalam rentetan pertama dengan 'a' dalam rentetan kedua. Rentetan itu kini "bbac" dan "abbc".

• Tukar "c" dalam rentetan pertama dengan "b" dalam rentetan kedua. Rentetan sekarang ialah "bbcb" dan "abac".

"bbcb" secara leksikografi lebih besar daripada "abac". Oleh itu, bilangan swap minimum yang diperlukan ialah 2, dan output program ialah "Bilangan minimum swap: 2".

Kesimpulan

Dalam artikel ini, kami meneroka masalah menentukan bilangan swap minimum yang diperlukan antara dua rentetan supaya satu rentetan secara leksikografi lebih besar daripada rentetan yang lain. Kami membincangkan strategi untuk menyelesaikan masalah, melaksanakannya dalam C++, dan menerangkan konsep dengan contoh. Soalan manipulasi rentetan seperti ini adalah perkara biasa dalam temu bual dan pengaturcaraan kompetitif, dan memahami konsep ini sangat bermanfaat.

Atas ialah kandungan terperinci Bilangan minimum pertukaran antara dua rentetan supaya satu rentetan lebih besar daripada yang lain. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!