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

Explication:

1. Calcul de la somme des préfixes : 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.

2. Itérer sur les divisions possibles : 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).

   • Pour chaque division, comptez les zéros dans la sous-chaîne de gauche ($zeroCountLeft).
   • Utilisez le $prefixOneCount précalculé pour calculer le nombre d'unités dans la sous-chaîne de droite.

3. Calcul du score : 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.

4. Résultat final : La fonction renvoie le score maximum trouvé lors de tous les fractionnements.

Complexité:

• Complexité temporelle : O(n)

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

• Complexité spatiale : O(n)

  • Le tableau de somme de préfixes nécessite O(n) espace supplémentaire.

Exemple:

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!