Rumah > Artikel > pembangunan bahagian belakang > 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:
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:
Contoh 2:
Contoh 3:
Kekangan:
Petunjuk:
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:
Bahagikan Rentetan kepada Bongkah: Memandangkan rentetan yang cantik boleh dibentuk daripada bongkah panjang 2, kita boleh mengulangi rentetan dalam langkah 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.
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:
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:
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!