Changement de lettres II

2381. Lettres changeantes II

Difficulté :Moyen

Sujets : Tableau, chaîne, somme de préfixe

Vous recevez une chaîne s de lettres anglaises minuscules et un tableau d'entiers 2D décalés où shifts[i] = [start_i, end_i, direction_i]. Pour chaque i, décaler les caractères en s du début de l'index_i à la fin de l'index_i (inclus) en avant si direction_i = 1, ou décale les caractères vers l'arrière si direction_i = 0.

Déplacer un caractère vers l'avant signifie le remplacer par la lettre suivante de l'alphabet (retourner pour que « z » devienne « a »). De même, décaler un caractère vers l'arrière signifie le remplacer par la lettre précédente de l'alphabet (retourner pour que « a » devienne « z »).

Renvoyer la chaîne finale après l'application de tous ces décalages vers s.

Exemple 1 :

• Entrée : s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]
• Sortie : "as"
• Explication : Tout d'abord, décalez les caractères de l'index 0 à l'index 1 vers l'arrière. Maintenant s = "zac".
  • Deuxièmement, déplacez les caractères de l'index 1 vers l'index 2 vers l'avant. Maintenant s = "zbd".
  • Enfin, déplacez les caractères de l'index 0 vers l'index 2 vers l'avant. Maintenant s = "as".

Exemple 2 :

• Entrée : s = "dztz", shifts = [[0,0,0],[1,1,1]]
• Sortie : "catz"
• Explication : Tout d'abord, décalez les caractères de l'index 0 à l'index 0 vers l'arrière. Maintenant s = "cztz".
  • Enfin, déplacez les caractères de l'index 1 à l'index 1 vers l'avant. Maintenant s = "catz".

Contraintes :

• 1 4
• shifts[i].length == 3
• 0 i i
• 0 i
• s se compose de lettres anglaises minuscules.

Indice :

1. Au lieu de décaler chaque caractère dans chaque équipe, pourriez-vous savoir quels caractères sont décalés et de combien dans toutes les équipes ?
2. Essayez de marquer le début et la fin de chaque équipe, puis effectuez une somme de préfixes des équipes.

Solution :

Nous devons éviter de décaler les caractères un par un à chaque décalage, car cela serait trop lent pour des entrées volumineuses. Au lieu de cela, nous pouvons utiliser une approche plus optimale en tirant parti d'une technique appelée somme des préfixes.

Mesures:

1. Marquer les limites de décalage : Au lieu de décaler chaque caractère immédiatement, nous marquons les effets de décalage au début et à la fin de chaque plage.
2. Appliquer la somme des préfixes : Après avoir marqué tous les décalages, nous pouvons calculer les décalages cumulés à chaque caractère en utilisant la technique de la somme des préfixes. Cela nous permet d'appliquer efficacement les décalages cumulés à chaque personnage.
3. Effectuer les décalages : Une fois que nous connaissons le décalage total pour chaque caractère, nous pouvons appliquer les décalages (vers l'avant ou vers l'arrière) à la chaîne.

Implémentons cette solution en PHP : 2381. Lettres changeantes II

<?php /**
 * @param String $s
 * @param Integer[][] $shifts
 * @return String
 */
function shiftingLetters($s, $shifts) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test the function
$s1 = "abc";
$shifts1 = [[0, 1, 0], [1, 2, 1], [0, 2, 1]];
echo shiftingLetters($s1, $shifts1) . "\n";  // Output: "ace"

$s2 = "dztz";
$shifts2 = [[0, 0, 0], [1, 1, 1]];
echo shiftingLetters($s2, $shifts2) . "\n";  // Output: "catz"
?>

Explication:

1. Pour chaque quart de travail [début, fin, direction], nous incrémenterons un tableau de décalage au début et décrémenterons à la fin 1. Cela nous permet de suivre le début et la fin de la plage de décalage.
2. Après avoir traité tous les décalages, nous appliquons une somme de préfixes sur le tableau de décalage pour obtenir le décalage cumulé à chaque index.
3. Enfin, nous appliquons le décalage cumulatif à chaque caractère de la chaîne.

Explication du code :

1. Analyse des entrées : Nous convertissons les chaînes d'entrée en un tableau de caractères pour une manipulation plus facile.
2. Shift Array : On initialise un tableau de décalage de taille n 1 à zéro. Ce tableau est utilisé pour suivre les effets de décalage. Pour chaque quart de travail [début, fin, direction], nous ajustons les valeurs à shift[start] et shift[end 1] pour refléter le début et la fin du quart de travail.
3. Somme des préfixes : Nous calculons le décalage total pour chaque caractère en itérant sur le tableau de décalage et en maintenant une somme cumulée de décalages.
4. Décalage de caractère : Pour chaque caractère de la chaîne, nous calculons le caractère décalé final à l'aide de la formule (ord(currentChar) - ord('a') totalShift) % 26, qui tient compte de la nature circulaire du alphabet.
5. Résultat de retour : La chaîne finale est obtenue en reconvertissant le tableau de caractères en chaîne et en le renvoyant.

Complexité temporelle :

• Complexité temporelle : O(n m), où n est la longueur de la chaîne s et m est le nombre de décalages. En effet, nous parcourons la chaîne et la liste des équipes une fois chacune.
• Complexité spatiale : O(n), où n est la longueur de la chaîne s, en raison de l'espace nécessaire pour le tableau de décalage.

Cette solution gère efficacement le problème même avec les limites supérieures des contraintes d'entrée.

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!