使琴弦平衡的最少交换次数

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 laksanakan penyelesaian ini dalam PHP: 1963. Bilangan Minimum Pertukaran untuk Menjadikan Rentetan Seimbang

<?php
/**
 * @param String $s
 * @return Integer
 */
function minSwaps($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$s1 = "][][";
echo minSwaps($s1); // Output: 1

$s2 = "]]][[[";
echo minSwaps($s2); // Output: 2

$s3 = "[]";
echo minSwaps($s3); // Output: 0
?>





  
  
  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
如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：


领英
GitHub



          

            
  

            
        
以上是使琴弦平衡的最少交换次数的详细内容。更多信息请关注PHP中文网其他相关文章！