


Supprimer les nœuds de la liste liée présente dans le tableau
3217. Supprimer les nœuds de la liste liée présente dans le tableau
Difficulté :Moyen
Sujets : Tableau, table de hachage, liste chaînée
Vous recevez un tableau de nombres entiers et le début d'une liste chaînée. Renvoie l'en-tête de la liste chaînée modifiée après avoir supprimé tous les nœuds de la liste chaînée qui ont une valeur qui existe en nombres.
Exemple 1 :
- Entrée : nums = [1,2,3], tête = [1,2,3,4,5]
- Sortie : [4,5]
-
Explication :
Supprimez les nœuds avec les valeurs 1, 2 et 3.
Exemple 2 :
- Entrée : Entrée : nums = [1], head = [1,2,1,2,1,2]
- Sortie : [2,2,2]
-
Explication :
Supprimez les nœuds de valeur 1.
Exemple 3 :
- Entrée : nums = [5], head = [1,2,3,4]
-
Sortie : [1,2,3,4]
Aucun nœud n'a la valeur 5.
Contraintes :
- 1 <= nums.length <= 105
- 1 <= nums[i] <= 105
- Tous les éléments numériques sont uniques.
- Le nombre de nœuds dans la liste donnée est compris entre [1, 105].
- 1 <= Node.val <= 105
- L'entrée est générée de telle sorte qu'il y ait au moins un nœud dans la liste chaînée qui a une valeur non présente en chiffres.
Indice :
- Ajoutez tous les éléments de nums dans un ensemble.
- Scannez la liste pour vérifier si l'élément actuel doit être supprimé en cochant l'ensemble.
Solution :
Nous devons parcourir la liste chaînée et supprimer tous les nœuds qui ont une valeur présente dans le tableau nums.
Approche:
- Jeu de hachage pour une recherche rapide : Puisque vérifier si une valeur existe en nombres doit être efficace, nous convertirons les nombres en un jeu de hachage. Cela permet la recherche O(1) pour chaque valeur.
- Parcourir la liste chaînée : Nous allons parcourir la liste chaînée et supprimer les nœuds dont les valeurs sont présentes dans l'ensemble de hachage.
- Manipulation du pointeur : lors de l'itération, nous ajusterons les pointeurs pour "ignorer" les nœuds qui correspondent aux valeurs du tableau nums.
Mesures:
- Convertissez les nombres en un jeu de hachage pour la recherche O(1).
- Parcourez la liste chaînée avec deux pointeurs : un pour le nœud actuel et un pour le nœud précédent pour aider à supprimer efficacement les nœuds.
- Pour chaque nœud, vérifiez si la valeur est dans le jeu de hachage. Si tel est le cas, mettez à jour le prochain nœud précédent pour ignorer le nœud actuel.
Implémentons cette solution en PHP : 3217. Supprimer les nœuds de la liste liée présents dans le tableau
val = $val; $this->next = $next; } } class Solution { /** * @param Integer[] $nums * @param ListNode $head * @return ListNode */ function removeElements($head, $nums) { ... ... ... /** * go to ./solution.php */ } } // Example usage: // Linked List: 1 -> 2 -> 3 -> 4 -> 5 $head = new ListNode(1); $head->next = new ListNode(2); $head->next->next = new ListNode(3); $head->next->next->next = new ListNode(4); $head->next->next->next->next = new ListNode(5); // Array nums: [1, 2, 3] $nums = [1, 2, 3]; $solution = new Solution(); $result = $solution->removeElements($head, $nums); // Function to print the linked list function printList($node) { while ($node !== null) { echo $node->val . " "; $node = $node->next; } } // Print the resulting linked list printList($result); // Output: 4 5 ?>Explication:
removeElements($head, $nums) :
- Nous convertissons d'abord les nombres en un jeu de hachage ($numSet = array_flip($nums);) pour des recherches rapides.
- Un nœud factice est créé et lié à la tête de liste. Cela permet de simplifier les cas extrêmes, comme la suppression du nœud principal.
- Le pointeur précédent suit le nœud avant celui actuel, nous permettant de supprimer le nœud actuel en l'ignorant dans la liste.
- Pour chaque nœud, on vérifie si sa valeur est dans numSet. Si tel est le cas, nous le supprimons en ajustant le pointeur prev->next pour ignorer le nœud actuel.
Cas Edge :
- Si le nœud principal doit être supprimé, le nœud factice garantit que la tête peut être retirée proprement tout en renvoyant la liste correcte.
- Gère les cas où plusieurs nœuds consécutifs doivent être supprimés.
Complexité :
- Complexité temporelle : O(n), où n est le nombre de nœuds dans la liste chaînée. Nous visitons chaque nœud une fois. La conversion de nombres en un ensemble prend O(m), où m est la taille des nombres.
- Complexité spatiale : O(m) pour stocker l'ensemble de nombres.
Exemple de procédure pas à pas :
Pour les nombres d'entrée = [1, 2, 3] et head = [1, 2, 3, 4, 5], l'algorithme :
- Commencez au nœud 1, vérifiez si 1 est en chiffres et supprimez-le.
- Déplacez-vous vers le nœud 2, vérifiez si 2 est en chiffres et supprimez-le.
- Déplacez-vous vers le nœud 3, vérifiez si 3 est en chiffres et supprimez-le.
- Déplacez-vous vers les nœuds 4 et 5, qui ne sont pas en chiffres, ils restent donc dans la liste.
La liste chaînée résultante est [4, 5].
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 :
- 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!

Outils d'IA chauds

Undresser.AI Undress
Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover
Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool
Images de déshabillage gratuites

Clothoff.io
Dissolvant de vêtements AI

Video Face Swap
Échangez les visages dans n'importe quelle vidéo sans effort grâce à notre outil d'échange de visage AI entièrement gratuit !

Article chaud

Outils chauds

Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise
Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP

Dreamweaver CS6
Outils de développement Web visuel

SublimeText3 version Mac
Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Sujets chauds

Alipay Php ...

JWT est une norme ouverte basée sur JSON, utilisée pour transmettre en toute sécurité des informations entre les parties, principalement pour l'authentification de l'identité et l'échange d'informations. 1. JWT se compose de trois parties: en-tête, charge utile et signature. 2. Le principe de travail de JWT comprend trois étapes: la génération de JWT, la vérification de la charge utile JWT et l'analyse. 3. Lorsque vous utilisez JWT pour l'authentification en PHP, JWT peut être généré et vérifié, et les informations sur le rôle et l'autorisation des utilisateurs peuvent être incluses dans l'utilisation avancée. 4. Les erreurs courantes incluent une défaillance de vérification de signature, l'expiration des jetons et la charge utile surdimensionnée. Les compétences de débogage incluent l'utilisation des outils de débogage et de l'exploitation forestière. 5. L'optimisation des performances et les meilleures pratiques incluent l'utilisation des algorithmes de signature appropriés, la définition des périodes de validité raisonnablement,

Le détournement de la session peut être réalisé via les étapes suivantes: 1. Obtenez l'ID de session, 2. Utilisez l'ID de session, 3. Gardez la session active. Les méthodes pour empêcher le détournement de la session en PHP incluent: 1. Utilisez la fonction Session_RegeReate_id () pour régénérer l'ID de session, 2. Stocker les données de session via la base de données, 3. Assurez-vous que toutes les données de session sont transmises via HTTPS.

La fonction d'énumération dans PHP8.1 améliore la clarté et la sécurité du type du code en définissant les constantes nommées. 1) Les énumérations peuvent être des entiers, des chaînes ou des objets, améliorant la lisibilité du code et la sécurité des types. 2) L'énumération est basée sur la classe et prend en charge des fonctionnalités orientées objet telles que la traversée et la réflexion. 3) L'énumération peut être utilisée pour la comparaison et l'attribution pour assurer la sécurité du type. 4) L'énumération prend en charge l'ajout de méthodes pour implémenter une logique complexe. 5) La vérification stricte et la gestion des erreurs peuvent éviter les erreurs courantes. 6) L'énumération réduit la valeur magique et améliore la maintenabilité, mais prêtez attention à l'optimisation des performances.

L'application du principe solide dans le développement de PHP comprend: 1. Principe de responsabilité unique (SRP): Chaque classe n'est responsable d'une seule fonction. 2. Principe ouvert et ferme (OCP): les changements sont réalisés par extension plutôt que par modification. 3. Principe de substitution de Lisch (LSP): les sous-classes peuvent remplacer les classes de base sans affecter la précision du programme. 4. Principe d'isolement d'interface (ISP): utilisez des interfaces à grain fin pour éviter les dépendances et les méthodes inutilisées. 5. Principe d'inversion de dépendance (DIP): les modules élevés et de bas niveau reposent sur l'abstraction et sont mis en œuvre par injection de dépendance.

Comment déboguer le mode CLI dans phpstorm? Lors du développement avec PHPStorm, nous devons parfois déboguer PHP en mode interface de ligne de commande (CLI) ...

Envoyant des données JSON à l'aide de la bibliothèque Curl de PHP dans le développement de PHP, il est souvent nécessaire d'interagir avec les API externes. L'une des façons courantes consiste à utiliser la bibliothèque Curl pour envoyer le post� ...

Liaison statique (statique: :) implémente la liaison statique tardive (LSB) dans PHP, permettant à des classes d'appel d'être référencées dans des contextes statiques plutôt que de définir des classes. 1) Le processus d'analyse est effectué au moment de l'exécution, 2) Recherchez la classe d'appel dans la relation de succession, 3) il peut apporter des frais généraux de performance.
