Bilangan minimum swap bersebelahan diperlukan untuk membalikkan rentetan

Memandangkan rentetan str, kita boleh membalikkan rentetan dengan hanya menukar aksara bersebelahan. Kita perlu mencari bilangan minimum pergerakan yang diperlukan untuk membalikkan rentetan, hanya dengan menukar aksara bersebelahan. Kami akan melaksanakan dua kaedah untuk mencari penyelesaian yang diperlukan dan memberikan penjelasan dan pelaksanaan kod tersebut.

Contoh Contoh

Input1: string str1 = “shkej”

Output: 10

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

Pertama, kami akan mengalihkan aksara terakhir ke kedudukan pertama, yang memerlukan 4 swap, dan kemudian rentetan akan menjadi "jshke". Kemudian kami akan mengalihkan 'e' ke kedudukan kedua, yang memerlukan 3 swap. Begitu juga, untuk 'k', kita memerlukan dua swap, manakala untuk 'h', hanya 1 swap diperlukan, dan jawapan akhir ialah 10.

Input2: string str1 = “abace”

Output: 6

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

Mula-mula kita akan menukar aksara pada indeks ke-2 dan mengalihkannya ke indeks terakhir, ini akan mengambil 2 swap dan rentetan akan menjadi "abcea". Kemudian kita menukar 'b' untuk 'e', ​​ia akan mengambil 2 swap dan rentetan akan menjadi "aceba". Kemudian lakukan 2 pertukaran lagi untuk mendapatkan rentetan terbalik terakhir, yang memerlukan sejumlah 6 pertukaran.

Terjemahan bahasa Cina bagi

Pendekatan Naif

ialah:

Pendekatan Naif

Kita telah melihat contoh di atas, sekarang mari kita lihat langkah-langkah yang diperlukan untuk melaksanakan kod yang betul.

• Pertama, kami akan mencipta fungsi yang akan mengambil rentetan yang diberikan sebagai parameter dan akan mengembalikan bilangan langkah minimum yang diperlukan sebagai nilai pulangan.

• Dalam fungsi ini kita akan mencipta salinan rentetan dan kemudian membalikkannya untuk dibandingkan dengan rentetan asal.

• Kami akan mencipta tiga pembolehubah, dua yang pertama akan digunakan untuk melelaran melalui rentetan dan yang terakhir akan digunakan untuk menyimpan bilangan langkah yang diperlukan.

• Dengan menggunakan gelung sementara, kami akan mengulangi rentetan yang diberikan dan terus melangkau bilangan lelaran yang sama seperti nilai indeks semasa untuk membalikkan rentetan.

• Kemudian kita akan menggunakan gelung sementara untuk menukar aksara bersebelahan sehingga 'j' mencapai 'i' dan menambah kiraan pada setiap pertukaran.

• Akhir sekali, kami akan mengembalikan nilai kiraan dan mencetaknya dalam fungsi utama.

Contoh

#include <bits/stdc++.h>
using namespace std;
// function to get the minimum number of swaps 
int minSwaps(string str){
   string temp = str;
   reverse(temp.begin(), temp.end()); // reversing the string 
   int i = 0, j = 0;
   int ans = 0;
   int len = str.size();
   while (i <len) {
      j = i;		
      // find the character that is equal to the current element 
      while (str[j] != temp[i]) {
         j++;
      }
      // iterating util the current i is equal to j
      while (i < j) {
         char tempc = str[j];
         str[j] = str[j - 1];
         str[j - 1] = tempc;
         j--;
         ans++;
      }
      i++;
   }
   return ans;
}
int main(){
   string str = "efabc"; // given string     
   // calling the function to find the minimum number of steps required 
   cout<<"The minimum number of steps required to reverse the given string by swapping the adjacent characters is "<<minSwaps(str)<<endl;
   return 0;
}

Output

The minimum number of steps required to reverse the given string by swapping the adjacent characters is 10

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N^2), dengan N ialah panjang rentetan yang diberikan. Kami menggunakan gelung while bersarang untuk memberikan faktor N semasa lelaran.

Kerumitan ruang kod di atas ialah O(N) kerana kami mencipta rentetan tambahan di sana untuk menyimpan penyongsangan rentetan yang diberikan.

NOTA - Pendekatan alternatif boleh dilakukan di sini, tetapi memerlukan penggunaan struktur data yang sangat maju. Konsep kaedah ini ialah kita boleh mulakan dari aksara terakhir dan semak sehingga aksara pertama memenuhi syarat. Kemudian secara teori kita boleh mengalihkan watak itu ke kedudukan terakhir dan menandakan kedudukan itu sebagai selesai dan menyimpan nilai itu dalam struktur data peringkat tinggi.

Kemudian untuk setiap watak kita akan dapati watak yang sama datang dari belakang yang belum ditandakan lagi dan kemudian tambahkan kiraan kepada jumlah elemen yang mengikutinya tolak bilangan elemen yang ditag.

Kesimpulan

Dalam tutorial ini, kami melaksanakan kod untuk mencari bilangan minimum langkah yang diperlukan untuk membalikkan rentetan yang diberikan dengan menukar aksara bersebelahan sahaja. Kami menggunakan gelung sambil bersarang dan membalikkan salinan rentetan yang diberikan untuk mencari penyelesaiannya. Kerumitan masa kod di atas ialah O(N^2), dengan N ialah saiz rentetan dan kerumitan ruang ialah O(N).

Atas ialah kandungan terperinci Bilangan minimum swap bersebelahan diperlukan untuk membalikkan rentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!