Bilangan Minimum Perubahan untuk Menjadikan Rentetan Binari Cantik

2914. Bilangan Minimum Perubahan untuk Menjadikan Rentetan Binari Cantik

Kesukaran: Sederhana

Topik: Rentetan

Anda diberi 0-indeks rentetan binari s yang mempunyai panjang genap.

Sebuah rentetan adalah cantik jika boleh membahagikannya menjadi satu atau lebih rentetan supaya:

• Setiap subrentetan mempunyai panjang sekata.
• Setiap subrentetan mengandungi sahaja 1 atau 0 sahaja.

Anda boleh menukar mana-mana aksara dalam s kepada 0 atau 1.

Kembalikan bilangan minimum perubahan yang diperlukan untuk menjadikan rentetan itu cantik.

Contoh 1:

• Input: s = "1001"
• Output: 2
• Penjelasan: Kami menukar s[1] kepada 1 dan s[3] kepada 0 untuk mendapatkan rentetan "1100".
  • Dapat dilihat bahawa rentetan "1100" itu cantik kerana kita boleh membahagikannya kepada "11|00".
  • Boleh dibuktikan bahawa 2 ialah bilangan minimum perubahan yang diperlukan untuk menjadikan rentetan itu cantik.

Contoh 2:

• Input: s = "10"
• Output: 1
• Penjelasan: Kami menukar s[1] kepada 1 untuk mendapatkan rentetan "11".
  • Dapat dilihat bahawa rentetan "11" itu cantik kerana kita boleh membahagikannya kepada "11".
  • Boleh dibuktikan bahawa 1 ialah bilangan minimum perubahan yang diperlukan untuk menjadikan rentetan itu cantik.

Contoh 3:

• Input: s = "0000"
• Output: 0
• Penjelasan: Kami tidak perlu membuat sebarang perubahan kerana rentetan "0000" sudah cantik.

Kekangan:

• 2 <= s.panjang <= 10⁵
• s mempunyai panjang sekata.
• s[i] sama ada '0' atau '1'.

Petunjuk:

1. Untuk mana-mana partition yang sah, memandangkan setiap bahagian mengandungi nombor genap aksara yang sama, kami boleh membahagikan lagi setiap bahagian kepada panjang tepat 2.
2. Selepas perasan pembayang pertama, kita boleh menguraikan keseluruhan rentetan menjadi bongkah terputus-putus bersaiz 2 dan mencari bilangan perubahan minimum yang diperlukan untuk menjadikan bongkah itu cantik.

Penyelesaian:

Kita perlu memastikan bahawa setiap pasangan aksara dalam rentetan binari s sama ada "00" atau "11". Jika sepasang tidak berada dalam salah satu daripada dua corak ini, kita perlu menukar salah satu watak untuk menjadikannya sepadan.

Berikut ialah pendekatan penyelesaian langkah demi langkah:

1. Bahagikan Rentetan kepada Bongkah: Memandangkan rentetan yang cantik boleh dibentuk daripada bongkah panjang 2, kita boleh mengulangi rentetan dalam langkah 2.

2. Kira Perubahan: Untuk setiap blok 2 aksara, kita perlu menentukan aksara majoriti (sama ada 0 atau 1). Kami akan menukar watak minoriti dalam blok agar sepadan dengan watak majoriti.

3. Kira Perubahan Minimum: Untuk setiap blok, jika kedua-dua aksara berbeza, kami memerlukan 1 pertukaran; jika ia sama, tiada perubahan diperlukan.

Mari laksanakan penyelesaian ini dalam PHP: 2914. Bilangan Minimum Perubahan untuk Menjadikan Rentetan Binari Cantik

  
  
  Penjelasan:



Definisi Fungsi: Kami mentakrifkan fungsi minChanges yang mengambil rentetan binari s.
Permulaan: Kami memulakan pembolehubah $changes untuk menjejaki bilangan perubahan yang diperlukan.

Lelaran Melalui Rentetan: Kami menggelung melalui rentetan, menambah sebanyak 2 setiap kali untuk menyemak setiap blok dua aksara:



$first ialah watak pada kedudukan semasa.

$second ialah watak di kedudukan seterusnya.


Semak Perubahan: Jika aksara dalam blok semasa berbeza, kami menambah pembilang $changes sebanyak 1.
Keputusan Pulangan: Akhirnya, kami mengembalikan jumlah perubahan yang diperlukan.



  
  
  Kerumitan:




Kerumitan Masa: O(n), dengan n ialah panjang rentetan, seperti kita mengulangi rentetan sekali.

Kerumitan Angkasa: O(1), kerana kami menggunakan jumlah ruang tambahan yang tetap.


Penyelesaian ini beroperasi dalam O(n) kerumitan masa, dengan n ialah panjang rentetan, menjadikannya cekap untuk kekangan yang diberikan.

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 Perubahan untuk Menjadikan Rentetan Binari Cantik. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!