Skor Maksimum Selepas Membahagikan Rentetan

1422. Markah Maksimum Selepas Membahagikan Rentetan

Kesukaran: Mudah

Topik: Rentetan, Jumlah Awalan

Diberi rentetan sifar dan satu, kembalikan skor maksimum selepas membahagikan rentetan kepada dua tak kosong subrentetan (iaitu kiri subrentetan dan kanan subrentetan).

Skor selepas membelah rentetan ialah bilangan sifar dalam subrentetan kiri ditambah dengan bilangan satu di kanan subrentetan.

Contoh 1:

• Input: s = "011101"
• Output: 5
• Penjelasan: Semua cara yang mungkin untuk memisahkan s kepada dua subrentetan bukan kosong ialah:
  • kiri = "0" dan kanan = "11101", skor = 1 4 = 5
  • kiri = "01" dan kanan = "1101", skor = 1 3 = 4
  • kiri = "011" dan kanan = "101", skor = 1 2 = 3
  • kiri = "0111" dan kanan = "01", skor = 1 1 = 2
  • kiri = "01110" dan kanan = "1", skor = 2 1 = 3

Contoh 2:

• Input: s = "00111"
• Output: 5
• Penjelasan: Apabila kiri = "00" dan kanan = "111", kita mendapat markah maksimum = 2 3 = 5

Contoh 3:

• Input: s = "1111"
• Output: 3

Kekangan:

• 2
• Rentetan s terdiri daripada aksara '0' dan '1' sahaja.

Petunjuk:

1. Prahitung jumlah awalan satu ('1').
2. Lelaran dari kiri ke kanan mengira bilangan sifar ('0'), kemudian gunakan jumlah awalan yang diprakira untuk mengira satu ('1'). Kemas kini jawapan.

Penyelesaian:

Kita boleh memanfaatkan pembayang yang diberikan dengan membuat prapengiraan jumlah awalan satu ('1') dalam rentetan. Begini cara kita boleh memecahkan penyelesaiannya:

Langkah-langkah:

1. Jumlah awalan satu: Prakirakan tatasusunan di mana setiap elemen pada indeks i mengandungi bilangan satu ('1') sehingga indeks i dalam rentetan.
2. Lelaran pada rentetan: Untuk setiap kedudukan i, layan subrentetan daripada 0 kepada i sebagai subrentetan "kiri" dan dari i 1 hingga hujung rentetan sebagai subrentetan "kanan".
   • Kira sifar dalam subrentetan kiri dengan hanya mengiranya semasa anda berulang.
   • Gunakan jumlah awalan untuk mengira yang dalam subrentetan kanan (dengan menolak jumlah awalan pada titik pisah daripada jumlah kiraan satu dalam rentetan).
3. Kira skor: Untuk setiap pemisahan yang mungkin, hitung skor sebagai bilangan sifar dalam subrentetan kiri ditambah bilangan satu dalam subrentetan kanan.
4. Kembalikan markah maksimum.

Mari laksanakan penyelesaian ini dalam PHP: 1422. Markah Maksimum Selepas Membahagikan Rentetan

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

// Test cases
$s1 = "011101";
$s2 = "00111";
$s3 = "1111";

echo "Input: $s1, Output: " . maxScore($s1) . PHP_EOL; // Output: 5
echo "Input: $s2, Output: " . maxScore($s2) . PHP_EOL; // Output: 5
echo "Input: $s3, Output: " . maxScore($s3) . PHP_EOL; // Output: 3
?>

Penjelasan:

1. Pengiraan jumlah awalan: Kami mengira jumlah awalan satu dalam tatasusunan $prefixOneCount, di mana setiap indeks menyimpan kiraan terkumpul satu sehingga titik itu.

2. Meletup atas kemungkinan pemisahan: Kami mula mengulangi setiap indeks i (dari 0 hingga n-2), di mana rentetan dipecahkan kepada bahagian kiri (dari 0 hingga i) dan bahagian kanan ( dari i 1 hingga n-1).

   • Untuk setiap pemisahan, kira sifar dalam subrentetan kiri ($zeroCountLeft).
   • Gunakan $prefixOneCount yang diprakira untuk mengira bilangan yang berada dalam subrentetan yang betul.

3. Pengiraan skor: Markah untuk setiap pemisahan dikira sebagai jumlah sifar di bahagian kiri dan satu di bahagian kanan. Kami mengemas kini skor maksimum yang ditemui semasa lelaran ini.

4. Keputusan akhir: Fungsi mengembalikan markah maksimum yang ditemui semasa semua pemisahan.

Kerumitan:

• Kerumitan Masa: O(n)

  • Prapengiraan jumlah awalan dan lelaran melalui rentetan kedua-duanya mengambil masa O(n).
  • Lelaran melalui rentetan untuk mengira markah juga memerlukan O(n).
  • Oleh itu, jumlah kerumitan masa ialah O(n), yang cekap untuk saiz input yang diberikan (n ≤ 500).

• Kerumitan Angkasa: O(n)

  • Susun atur jumlah awalan memerlukan O(n) ruang tambahan.

Contoh:

echo maxScore("011101"); // Output: 5
echo maxScore("00111");  // Output: 5
echo maxScore("1111");   // Output: 3

Penyelesaian ini adalah optimum dan menangani masalah dalam kekangan.

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 Skor Maksimum Selepas Membahagikan Rentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!