Bilangan Minimum Pertukaran untuk Menjadikan Rentetan Seimbang

1963. Bilangan Minimum Pertukaran untuk Menjadikan Rentetan Seimbang

Kesukaran: Sederhana

Topik: Dua Penunjuk, Rentetan, Tindanan, Tamak

Anda diberi 0-diindeks rentetan s genap panjang n. Rentetan terdiri daripada tepat n / 2 kurungan pembukaan '[' dan n / 2 kurungan penutup ']'.

Rentetan dipanggil seimbang jika dan hanya jika:

• Ia adalah rentetan kosong, atau
• Ia boleh ditulis sebagai AB, di mana kedua-dua A dan B ialah seimbang rentetan, atau
• Ia boleh ditulis sebagai [C], dengan C ialah rentetan seimbang.

Anda boleh menukar kurungan pada mana-mana dua indeks mana-mana bilangan kali.

Kembalikan bilangan minimum swap untuk menjadikan s seimbang.

Contoh 1:

• Input: s = "][][]["
• Output: 1
• Penjelasan: Anda boleh membuat rentetan seimbang dengan menukar indeks 0 dengan indeks 3.
  • Rentetan yang terhasil ialah "[[]]".

Contoh 2:

• Input: s = "]]][[["
• Output: 2
• Penjelasan: Anda boleh melakukan perkara berikut untuk menjadikan rentetan seimbang:
  • Tukar indeks 0 dengan indeks 4. s = "[]][][".
  • Tukar indeks 1 dengan indeks 5. s = "[[][]]".
  • Rentetan yang terhasil ialah "[[][]]".

Contoh 3:

• Input: s = "[]"
• Output: 0
• Penjelasan: Rentetan sudah seimbang.

Kekangan:

• n == s.panjang
• 2 <= n <= 10⁶
• n adalah genap.
• s[i] ialah sama ada '[' atau ']'.
• Bilangan kurungan pembukaan '[' bersamaan dengan n / 2, dan bilangan kurungan penutup ']' bersamaan dengan n / 2.

Petunjuk:

1. Lelaran pada rentetan dan jejaki bilangan kurungan pembukaan dan penutup pada setiap langkah.
2. Jika bilangan kurungan penutup semakin besar, anda perlu membuat pertukaran.
3. Tukarnya dengan kurungan bukaan yang paling hampir dengan penghujung s.

Penyelesaian:

Kita boleh menggunakan pendekatan dua mata, yang cekap memandangkan kekangan.

Pendekatan:

1. Imbangan Jejak: Sambil kita mengulangi rentetan, kita boleh menjejaki keseimbangan antara kurungan pembukaan dan penutup:

   • Naikkan baki apabila menemui '['.
   • Kurangkan baki apabila menemui ']'.

2. Kenalpasti Ketidakseimbangan: Apabila baki menjadi negatif, ini menunjukkan bahawa terdapat lebih banyak kurungan penutup ']' daripada kurungan pembukaan '[' pada titik itu dalam rentetan. Di sinilah kita perlu menukar kurungan untuk menjadikan rentetan seimbang.

3. Pertukaran Kira: Untuk membetulkan ketidakseimbangan:

   • Simpan ketidakseimbangan maks_kaunter untuk menjejaki ketidakseimbangan maksimum yang diperhatikan semasa lelaran.
   • Bilangan swap yang diperlukan adalah sama dengan (max_imbalance 1) / 2, yang secara berkesan memberikan bilangan swap minimum yang diperlukan untuk menjadikan rentetan seimbang.

Mari kita laksanakan penyelesaian ini dalam PHP: 1963. Bilangan Minimum Pertukaran untuk Menjadikan Rentetan Seimbang

  
  
  Penjelasan:




Penjejakan Baki:



baki menjejaki perbezaan antara bilangan '[' dan ']'.
Jika baki menjadi negatif, ini menunjukkan bahawa terdapat lebih banyak ']' daripada '[' pada ketika itu.



Kira Ketidakseimbangan Maksimum:



max_imbalance menyimpan ketidakseimbangan terbesar yang dihadapi semasa lelaran.
Jika baki menjadi negatif, kemas kini max_imbalance dengan max_imbalance atau -balance yang lebih besar.



Kira Swap:


Untuk membetulkan ketidakseimbangan, pertukaran minimum yang diperlukan ialah (ketidakseimbangan_maks 1) / 2.





  
  
  Kerumitan Masa:



Kerumitan masa ialah O(n), dengan n ialah panjang rentetan. Kami mengulangi rentetan sekali untuk menentukan ketidakseimbangan_maks.
Kerumitan ruang ialah O(1) kerana kami menggunakan beberapa pembolehubah untuk menjejaki keseimbangan dan ketidakseimbangan maksimum.


Penyelesaian ini memastikan kami memenuhi kekangan, walaupun untuk input yang besar.

Pautan Kenalan
Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci Bilangan Minimum Pertukaran untuk Menjadikan Rentetan Seimbang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!