Score maximum après avoir divisé une chaîne

1422. Score maximum après avoir divisé une chaîne

Difficulté :Facile

Sujets : Chaîne, somme de préfixe

Étant donné une chaîne s de zéros et de uns, renvoie le score maximum après avoir divisé la chaîne en deux non vides sous-chaînes (c'est-à-dire gauche sous-chaîne et droitesous-chaîne).

Le score après avoir divisé une chaîne est le nombre de zéros dans la sous-chaîne gauche plus le nombre de uns dans la droite sous-chaîne.

Exemple 1 :

• Entrée : s = "011101"
• Sortie : 5
• Explication : Toutes les manières possibles de diviser s en deux sous-chaînes non vides sont :
  • gauche = "0" et droite = "11101", score = 1 4 = 5
  • gauche = "01" et droite = "1101", score = 1 3 = 4
  • gauche = "011" et droite = "101", score = 1 2 = 3
  • gauche = "0111" et droite = "01", score = 1 1 = 2
  • gauche = "01110" et droite = "1", score = 2 1 = 3

Exemple 2 :

• Entrée : s = "00111"
• Sortie : 5
• Explication :Quand gauche = "00" et droite = "111", on obtient le score maximum = 2 3 = 5

Exemple 3 :

• Entrée : s = "1111"
• Sortie : 3

Contraintes :

• 2 <= s.length <= 500
• La chaîne s est composée uniquement des caractères « 0 » et « 1 ».

Indice :

1. Précalculez une somme de préfixes de uns (« 1 »).
2. Parcourez de gauche à droite en comptant le nombre de zéros (« 0 »), puis utilisez la somme de préfixes précalculée pour compter les uns (« 1 »). Mettez à jour la réponse.

Solution :

Nous pouvons exploiter l'indice fourni en précalculant une somme de préfixes de uns (« 1 ») dans la chaîne. Voici comment nous pouvons décomposer la solution :

Mesures:

1. Somme des préfixes des uns : précalculez un tableau où chaque élément à l'index i contient le nombre de uns ("1") jusqu'à l'index i dans la chaîne.
2. Itérer sur la chaîne : Pour chaque position i, traitez la sous-chaîne de 0 à i comme la sous-chaîne "gauche" et de i 1 à la fin de la chaîne comme la sous-chaîne "droite".
   • Comptez les zéros dans la sous-chaîne de gauche en les comptant simplement au fur et à mesure de votre itération.
   • Utilisez la somme des préfixes pour compter les uns dans la sous-chaîne de droite (en soustrayant la somme des préfixes au point de partage du nombre total de uns dans la chaîne).
3. Calculez le score : Pour chaque division possible, calculez le score comme le nombre de zéros dans la sous-chaîne de gauche plus le nombre de un dans la sous-chaîne de droite.
4. Renvoyer le score maximum.

Implémentons cette solution en PHP : 1422. Score maximum après avoir divisé une chaîne

<?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
?>




<h3>
  
  
  Explication:
</h3>

<ol>
<li><p><strong>Calcul de la somme des préfixes</strong> : Nous calculons la somme des préfixes des uns dans le tableau $prefixOneCount, où chaque index contient le nombre cumulé de uns jusqu'à ce point.</p></li>
<li>
<p><strong>Itérer sur les divisions possibles</strong> : Nous commençons à parcourir chaque index i (de 0 à n-2), où la chaîne est divisée en une partie gauche (de 0 à i) et une partie droite ( de i 1 à n-1).</p>

<ul>
<li>Pour chaque division, comptez les zéros dans la sous-chaîne de gauche ($zeroCountLeft).</li>
<li>Utilisez le $prefixOneCount précalculé pour calculer le nombre d'unités dans la sous-chaîne de droite.</li>
</ul>
</li>
<li><p><strong>Calcul du score</strong> : Le score de chaque division est calculé comme la somme des zéros dans la partie gauche et des uns dans la partie droite. Nous mettons à jour le score maximum rencontré lors de cette itération.</p></li>
<li><p><strong>Résultat final</strong> : La fonction renvoie le score maximum trouvé lors de tous les fractionnements.</p></li>
</ol>

<h3>
  
  
  Complexité:
</h3>

<ul>
<li>
<p><strong>Complexité temporelle</strong> : <em><strong>O(n)</strong></em></p>

<ul>
<li>Le précalcul des sommes de préfixes et l'itération dans la chaîne prennent tous deux <em><strong>O(n)</strong></em>.</li>
<li>Itérer dans la chaîne pour calculer les scores prend également O(n).</li>
<li>Ainsi, la complexité temporelle totale est O(n), ce qui est efficace pour la taille d'entrée donnée (n ≤ 500).</li>
</ul>


</li>

<li>

<p><strong>Complexité spatiale</strong> : <em><strong>O(n)</strong></em></p>

<ul>
<li>Le tableau de somme de préfixes nécessite <em><strong>O(n)</strong></em> espace supplémentaire.</li>
</ul>


</li>

</ul>

<h3>
  
  
  Exemple:
</h3>



<pre class="brush:php;toolbar:false">echo maxScore("011101"); // Output: 5
echo maxScore("00111");  // Output: 5
echo maxScore("1111");   // Output: 3

Cette solution est optimale et gère le problème dans les limites des contraintes.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!