Maison développement back-end tutoriel php Supprimer les nœuds de la liste liée présente dans le tableau

Supprimer les nœuds de la liste liée présente dans le tableau

Sep 07, 2024 pm 04:30 PM

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 : Delete Nodes From Linked List Present in Array 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 : Delete Nodes From Linked List Present in Array Supprimez les nœuds de valeur 1.

Exemple 3 :

  • Entrée : nums = [5], head = [1,2,3,4]
  • Sortie : [1,2,3,4] Delete Nodes From Linked List Present in Array 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 :

  1. Ajoutez tous les éléments de nums dans un ensemble.
  2. 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:

  1. 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.
  2. 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.
  3. 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:

  1. Convertissez les nombres en un jeu de hachage pour la recherche O(1).
  2. 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.
  3. 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:

  1. 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.
  2. 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.
  3. 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 :

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

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

Video Face Swap

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

<🎜>: Bubble Gum Simulator Infinity - Comment obtenir et utiliser les clés royales
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
<🎜>: Grow A Garden - Guide de mutation complet
3 Il y a quelques semaines By DDD
Nordhold: Système de fusion, expliqué
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Mandragora: Whispers of the Witch Tree - Comment déverrouiller le grappin
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

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

Sujets chauds

Tutoriel Java
1672
14
Tutoriel PHP
1277
29
Tutoriel C#
1257
24
Expliquez le hachage de mot de passe sécurisé dans PHP (par exemple, Password_Hash, Password_verify). Pourquoi ne pas utiliser MD5 ou SHA1? Expliquez le hachage de mot de passe sécurisé dans PHP (par exemple, Password_Hash, Password_verify). Pourquoi ne pas utiliser MD5 ou SHA1? Apr 17, 2025 am 12:06 AM

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.

Comment fonctionne la résistance au type PHP, y compris les types scalaires, les types de retour, les types d'union et les types nullables? Comment fonctionne la résistance au type PHP, y compris les types scalaires, les types de retour, les types d'union et les types nullables? Apr 17, 2025 am 12:25 AM

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 et Python: différents paradigmes expliqués PHP et Python: différents paradigmes expliqués Apr 18, 2025 am 12:26 AM

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: exemples de code et comparaison PHP et Python: exemples de code et comparaison Apr 15, 2025 am 12:07 AM

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.

Comment empêchez-vous l'injection SQL en PHP? (Déclarations préparées, APD) Comment empêchez-vous l'injection SQL en PHP? (Déclarations préparées, APD) Apr 15, 2025 am 12:15 AM

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: Gestion des bases de données et logique côté serveur PHP: Gestion des bases de données et logique côté serveur Apr 15, 2025 am 12:15 AM

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.

Objectif de PHP: Construire des sites Web dynamiques Objectif de PHP: Construire des sites Web dynamiques Apr 15, 2025 am 12:18 AM

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.

Choisir entre PHP et Python: un guide Choisir entre PHP et Python: un guide Apr 18, 2025 am 12:24 AM

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.

See all articles