Minimumkan bilangan operasi yang diperlukan supaya dua rentetan yang diberikan adalah pilih atur antara satu sama lain

Dalam artikel ini, kita akan membincangkan cara meminimumkan bilangan operasi yang diperlukan untuk menjajarkan dua rentetan yang diberikan antara satu sama lain. Kami akan mengikuti pendekatan langkah demi langkah dan menyediakan pelaksanaan dalam kod C++. Kami juga akan menyediakan contoh kes ujian untuk membantu memahami masalah dan penyelesaiannya.

Pernyataan Masalah

Memandangkan dua rentetan s1 dan s2, kita perlu mencari bilangan operasi minimum yang diperlukan untuk menjadikan s1 dan s2 sejajar antara satu sama lain. Kita boleh melakukan dua operasi: menukar mana-mana dua aksara s1, atau menukar mana-mana dua aksara s2.

Metodologi dan Pelaksanaan

Untuk menyelesaikan masalah ini, kita perlu mengira bilangan aksara yang tidak wujud dalam dua rentetan, iaitu perbezaan kekerapan kejadian aksara dalam dua rentetan. Bilangan swap minimum yang diperlukan untuk membuat dua rentetan permute antara satu sama lain adalah sama dengan separuh kiraan ini, kerana kita boleh menukar aksara dalam mana-mana rentetan untuk menjadikannya sama.

Pertama, kami akan menggunakan dua tatasusunan untuk mengira kekerapan aksara dalam dua rentetan. Kami kemudian akan melelar melalui dua tatasusunan dan menambah perbezaan mutlak antara frekuensi aksara kepada pembolehubah. Pembolehubah ini akan menyimpan bilangan aksara yang tidak terdapat dalam kedua-dua rentetan.

Selepas mengira kiraan, kami mengembalikan separuh daripadanya sebagai bilangan swap minimum yang diperlukan untuk kedua-dua rentetan itu diubah suai antara satu sama lain.

Contoh

Berikut ialah pelaksanaan kod C++ bagi kaedah di atas -

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

int countMinSwaps(string s1, string s2) {
   int freq1[26] = {0}, freq2[26] = {0}, count = 0;
   for (char c : s1) {
      freq1[c - 'a']++;
   }
   for (char c : s2) {
      freq2[c - 'a']++;
   }
   for (int i = 0; i < 26; i++) {
      count += abs(freq1[i] - freq2[i]);
   }
   return count / 2;
}

int main() {
   string s1 = "hello";
   string s2 = "world";
   int minSwaps = countMinSwaps(s1, s2);
   cout << "Minimum number of swaps required: " << minSwaps << endl;
   return 0;
}

Output

Minimum number of swaps required: 3

Contoh kes ujian

Mari kita pertimbangkan contoh rentetan "hello" dan "world" untuk kes ujian ini.

Tatasusunan kekerapan dua rentetan adalah seperti berikut -

freq1 = {0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
freq2 = {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 2, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}

Kita dapat melihat bahawa aksara "l" muncul dengan frekuensi 2 dalam s1 tetapi hanya 1 dalam s2, manakala aksara "r" muncul dengan frekuensi 1 dalam s2 tetapi tiada dalam s1. Oleh itu, bilangan aksara yang tidak terdapat dalam kedua-dua rentetan ialah 3.

Oleh itu, bilangan swap minimum yang diperlukan untuk dua rentetan diubah suai antara satu sama lain ialah 1. Kita boleh menukar "l" dalam s1 dengan "r" dalam s2 untuk mendapatkan rentetan "herlo" dan "wolld", yang merupakan pilihatur antara satu sama lain.

Kesimpulan

Dalam artikel ini, kami membincangkan cara meminimumkan bilangan operasi tertentu yang diperlukan untuk menjajarkan dua rentetan yang diberikan antara satu sama lain. Kami mengikuti pendekatan langkah demi langkah dan menyediakan pelaksanaan kod C++. Kami juga menyediakan contoh kes ujian untuk membantu memahami masalah dan penyelesaiannya. Masalahnya boleh diselesaikan dalam kerumitan masa O(n) dan kerumitan ruang O(1).

Atas ialah kandungan terperinci Minimumkan bilangan operasi yang diperlukan supaya dua rentetan yang diberikan adalah pilih atur antara satu sama lain. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!