


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











Dans PHP, Password_Hash et Password_verify Les fonctions doivent être utilisées pour implémenter le hachage de mot de passe sécurisé, et MD5 ou SHA1 ne doit pas être utilisé. 1) Password_hash génère un hachage contenant des valeurs de sel pour améliorer la sécurité. 2) Password_verify Vérifiez le mot de passe et assurez-vous la sécurité en comparant les valeurs de hachage. 3) MD5 et SHA1 sont vulnérables et manquent de valeurs de sel, et ne conviennent pas à la sécurité de mot de passe moderne.

Le type PHP invite à améliorer la qualité et la lisibilité du code. 1) Conseils de type scalaire: Depuis PHP7.0, les types de données de base sont autorisés à être spécifiés dans les paramètres de fonction, tels que INT, Float, etc. 2) Invite de type de retour: Assurez la cohérence du type de valeur de retour de fonction. 3) Invite de type d'union: Depuis PHP8.0, plusieurs types peuvent être spécifiés dans les paramètres de fonction ou les valeurs de retour. 4) Invite de type nullable: permet d'inclure des valeurs nulles et de gérer les fonctions qui peuvent renvoyer les valeurs nulles.

PHP est principalement la programmation procédurale, mais prend également en charge la programmation orientée objet (POO); Python prend en charge une variété de paradigmes, y compris la POO, la programmation fonctionnelle et procédurale. PHP convient au développement Web, et Python convient à une variété d'applications telles que l'analyse des données et l'apprentissage automatique.

PHP et Python ont leurs propres avantages et inconvénients, et le choix dépend des besoins du projet et des préférences personnelles. 1.Php convient au développement rapide et à la maintenance des applications Web à grande échelle. 2. Python domine le domaine de la science des données et de l'apprentissage automatique.

L'utilisation de déclarations de prétraitement et l'APD dans PHP peut effectivement empêcher les attaques d'injection SQL. 1) Utilisez PDO pour vous connecter à la base de données et définir le mode d'erreur. 2) Créez des instructions de prétraitement via la méthode de préparation et transmettez des données à l'aide des espaces réservés et exécutez des méthodes. 3) Traitez les résultats de la requête et assurez la sécurité et les performances du code.

PHP utilise les extensions MySQLI et PDO pour interagir dans les opérations de base de données et le traitement de la logique côté serveur, et traite la logique côté serveur via des fonctions telles que la gestion de session. 1) Utilisez MySQLI ou PDO pour vous connecter à la base de données et exécuter les requêtes SQL. 2) Gérer les demandes HTTP et l'état de l'utilisateur via la gestion de session et d'autres fonctions. 3) Utiliser les transactions pour assurer l'atomicité des opérations de base de données. 4) Empêcher l'injection de SQL, utiliser les connexions de gestion des exceptions et de clôture pour le débogage. 5) Optimiser les performances via l'indexation et le cache, écrivez du code très lisible et effectuez une gestion des erreurs.

PHP est utilisé pour créer des sites Web dynamiques, et ses fonctions principales incluent: 1. Générer du contenu dynamique et générer des pages Web en temps réel en se connectant à la base de données; 2. Traiter l'interaction utilisateur et les soumissions de formulaires, vérifier les entrées et répondre aux opérations; 3. Gérer les sessions et l'authentification des utilisateurs pour offrir une expérience personnalisée; 4. Optimiser les performances et suivre les meilleures pratiques pour améliorer l'efficacité et la sécurité du site Web.

PHP convient au développement Web et au prototypage rapide, et Python convient à la science des données et à l'apprentissage automatique. 1.Php est utilisé pour le développement Web dynamique, avec une syntaxe simple et adapté pour un développement rapide. 2. Python a une syntaxe concise, convient à plusieurs champs et a un écosystème de bibliothèque solide.
