Dalam artikel ini, kami akan menyelami masalah manipulasi rentetan yang menarik dalam C++. Pernyataan masalah ialah "Minimumkan penyingkiran aksara bukan bersebelahan untuk menjadikan rentetan yang diberikan kosong". Soalan ini ialah cara terbaik untuk meningkatkan pemahaman anda tentang rentetan, penyingkiran aksara dan pemikiran algoritma.
Memandangkan rentetan, tugasnya adalah untuk meminimumkan bilangan operasi pengalihan keluar aksara bersebelahan yang tidak sama yang diperlukan untuk menjadikan rentetan yang diberikan kosong Dalam satu operasi, anda boleh mengalih keluar mana-mana dua aksara bersebelahan yang tidak sama.
Penyelesaian kepada masalah ini adalah dengan menggunakan struktur data tindanan. Kami mengulangi aksara rentetan dan untuk setiap aksara, jika timbunan tidak kosong dan aksara atas timbunan tidak sama dengan aksara semasa, kami mengeluarkan watak teratas daripada timbunan. Jika tidak, tolak aksara semasa ke tindanan. Bilangan operasi yang diperlukan ialah bilangan aksara yang tinggal pada timbunan akhir.
#include <iostream> #include <stack> #include <string> using namespace std; int minimizeRemovals(string str) { stack<char> s; for (char c : str) { if (!s.empty() && s.top() != c) { s.pop(); } else { s.push(c); } } return s.size(); } int main() { string str = "abba"; int operations = minimizeRemovals(str); cout << "The minimum number of removal operations is: " << operations << endl; return 0; }
The minimum number of removal operations is: 0
Apabila kami melepasi rentetan ini untuk meminimumkan fungsi Removals, ia akan berulang ke atas aksara rentetan itu. Prosesnya adalah seperti berikut −
Ia menolak 'a' ke atas timbunan.
Kemudian ia menolak 'b' ke atas tindanan kerana 'b' tidak sama dengan elemen di bahagian atas tindanan ('a').
Apabila 'b' seterusnya ditemui, ia melihat bahagian atas tindanan juga adalah 'b', jadi ia tidak menjalankan operasi pengalih keluar dan 'b' ditolak ke tindanan.
Sekarang bahagian atas tindanan ialah 'b', dan aksara seterusnya ialah 'a' Memandangkan 'a' tidak sama dengan 'b', ia melakukan operasi alih keluar dengan memunculkan bahagian atas tindanan daripada timbunan ialah 'b'.
Akhir sekali, aksara 'a' yang tidak sama dengan elemen teratas tindanan ('b') ditemui dalam rentetan. Oleh itu, ia menjalankan operasi penyingkiran dan memaparkan elemen teratas timbunan.
Di penghujung fungsi, tiada aksara yang tinggal dalam timbunan, menunjukkan bahawa semua aksara bersebelahan yang tidak sama telah dialih keluar daripada rentetan Oleh itu, fungsi mengembalikan 0, iaitu bilangan minimum operasi pengalihan keluar yang diperlukan rentetan yang diberikan kosong.
Soalan ini memberikan peluang yang baik untuk menggunakan struktur data tindanan untuk operasi rentetan. Ini ialah soalan yang bagus untuk mempraktikkan kemahiran pengekodan C++ anda dan memahami cara menggunakan tindanan untuk menyelesaikan masalah.
Atas ialah kandungan terperinci Terjemah yang berikut ke dalam bahasa Cina: Minimumkan bilangan kali aksara serupa bukan bersebelahan dialih keluar supaya rentetan yang diberikan menjadi rentetan kosong. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!