Minimumkan penggantian aksara kepada huruf terdekatnya, menjadikan rentetan itu sebagai palindrom

Dalam artikel ini, kita akan membincangkan masalah algoritma yang menarik: "Minikan penggantian aksara dengan abjad terdekatnya untuk membuat palindrom rentetan." Masalah ini menarik kerana ia melibatkan operasi rentetan, semakan Palindrom dan konsep watak nilai ASCII. Mari kita mendalami isu ini.

Pernyataan Masalah

Diberi rentetan, tugasnya adalah untuk menukarnya menjadi palindrom dengan bilangan penggantian minimum. Penggantian ini dicapai dengan menukar aksara kepada abjad terdekatnya.

Memahami masalah

Palindrom ialah urutan perkataan, frasa, nombor atau aksara lain yang dibaca ke belakang sama seperti ke hadapan. Matlamat kami adalah untuk meminimumkan jumlah penggantian yang diperlukan untuk menukar rentetan yang diberikan kepada palindrom.

Sebagai contoh, pertimbangkan rentetan "abc". Untuk menukarnya kepada palindrom, kita boleh menggantikan "c" dengan "a", yang memerlukan dua penggantian ("c" kepada "b" dan "b" kepada "a"). Oleh itu, bilangan penggantian minimum ialah 2.

Kaedah Algoritma

Untuk menyelesaikan masalah ini, kami akan menggunakan kaedah dua penunjuk. Berikut adalah langkah-langkahnya -

• Mulakan dua penunjuk, satu pada permulaan rentetan dan satu lagi di hujung rentetan.

• Bandingkan watak pada penunjuk.

• Jika sama, gerakkan penunjuk ke dalam.

• Jika mereka tidak sama, gantikan aksara lebih jauh dari 'a' dengan aksara yang lebih dekat dan tambahkan bilangan penggantian. Juga, gerakkan penunjuk ke dalam.

• Ulang langkah 2-4 sehingga penunjuk mula tidak kurang daripada penunjuk akhir.

Contoh

Ini adalah kod C++ yang melaksanakan kaedah di atas -

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

int makePalindrome(string str) {
   int len = str.size();
   int res = 0;
   for (int i = 0, j = len - 1; i < j; i++, j--) {
      res += abs(str[i] - str[j]);
   }
   return res;
}

int main() {
   string str="abcde";
   cout << "Minimum replacements: " << makePalindrome(str);
   return 0;
}

Output

Minimum replacements: 6

Contoh kes ujian

Mari kita jalankan contoh -

Pertimbangkan rentetan "abcde". Program di atas akan mengeluarkan "Penggantian minimum: 4". Inilah sebabnya -

• Bandingkan "a" dan "e". Mereka tidak sama, jadi gantikan 'e' dengan 'a'. Ini memerlukan 4 penggantian. Rentetan kami kini "abcda".

• Bandingkan "b" dan "d". Mereka tidak sama, jadi gantikan 'd' dengan 'b'. Ini memerlukan 2 penggantian. Rentetan kami kini "abcba".

• Kini, rentetan itu ialah palindrom. Oleh itu, jumlah minimum penggantian ialah 4 + 2 = 6.

Ingat bahawa bilangan penggantian dikira berdasarkan perbezaan mutlak nilai ASCII aksara.

Kesimpulan

Soalan ini adalah contoh yang baik tentang bagaimana manipulasi rentetan mudah dan teknik dua mata boleh menyelesaikan masalah yang agak kompleks. Mengetahui soalan-soalan ini bukan sahaja akan membantu dalam temu bual pengekodan tetapi juga meningkatkan kemahiran menyelesaikan masalah anda secara keseluruhan.

Atas ialah kandungan terperinci Minimumkan penggantian aksara kepada huruf terdekatnya, menjadikan rentetan itu sebagai palindrom. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!