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 !

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)

Expliquez les jetons Web JSON (JWT) et leur cas d'utilisation dans les API PHP. Expliquez les jetons Web JSON (JWT) et leur cas d'utilisation dans les API PHP. Apr 05, 2025 am 12:04 AM

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,

Comment fonctionne le détournement de session et comment pouvez-vous l'atténuer en PHP? Comment fonctionne le détournement de session et comment pouvez-vous l'atténuer en PHP? Apr 06, 2025 am 12:02 AM

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.

Que sont les énumérations (enums) dans PHP 8.1? Que sont les énumérations (enums) dans PHP 8.1? Apr 03, 2025 am 12:05 AM

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.

Décrivez les principes solides et comment ils s'appliquent au développement de PHP. Décrivez les principes solides et comment ils s'appliquent au développement de PHP. Apr 03, 2025 am 12:04 AM

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? Comment déboguer le mode CLI dans phpstorm? Apr 01, 2025 pm 02:57 PM

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) ...

Comment envoyer une demande post contenant des données JSON à l'aide de la bibliothèque Curl de PHP? Comment envoyer une demande post contenant des données JSON à l'aide de la bibliothèque Curl de PHP? Apr 01, 2025 pm 03:12 PM

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� ...

Expliquez la liaison statique tardive en PHP (statique: :). Expliquez la liaison statique tardive en PHP (statique: :). Apr 03, 2025 am 12:04 AM

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.

See all articles