IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Énoncé incompréhensible pour moi


Sujet :

Algorithmes et structures de données

  1. #1
    Membre du Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    février 2021
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Meurthe et Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Boutique - Magasin

    Informations forums :
    Inscription : février 2021
    Messages : 25
    Points : 46
    Points
    46
    Par défaut Énoncé incompréhensible pour moi
    Bonjour à la communauté

    vu sur letscode :

    Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

    Notice that the solution set must not contain duplicate triplets.


    pour [-1,0,1,2,-1,-4]

    on devrais obtenir ça [[-1,-1,2],[-1,0,1]]


    Je ne comprend pas cette condition : such that i != j, i != k, and j != k

    cordialement

  2. #2
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    25 951
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 25 951
    Points : 181 549
    Points
    181 549
    Par défaut


    Ca veut dire que tu dois prendre des éléments distincts dans ta liste (sans compter la valeur, mais uniquement la position dans la liste).
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  3. #3
    Membre du Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    février 2021
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Meurthe et Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Boutique - Magasin

    Informations forums :
    Inscription : février 2021
    Messages : 25
    Points : 46
    Points
    46
    Par défaut
    Citation Envoyé par dourouc05 Voir le message
    Ca veut dire que tu dois prendre des éléments distincts dans ta liste (sans compter la valeur, mais uniquement la position dans la liste).
    merci de ta réponse

    je vais réfléchir à ça demain je tombe de sommeil

  4. #4
    Membre averti
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    122
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 122
    Points : 356
    Points
    356
    Par défaut
    C'est un sujet sympatoche …
    Ma première idée plutôt brute me donne une solution en O(n² logn) temps et O(1) espace, puis ensuite j'en ai une autre en O(n²) temps et O(n) espace, mais on peut se débrouiller en juste O(n²) temps et O(1) espace je pense …
    à creuser …
    fais nous part de tes avancées 👍

  5. #5
    Membre du Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    février 2021
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Meurthe et Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Boutique - Magasin

    Informations forums :
    Inscription : février 2021
    Messages : 25
    Points : 46
    Points
    46
    Par défaut
    qqu pourrait me dire pk par exemple [-1,-1,0] n'est pas accepté ?

  6. #6
    Membre averti
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    122
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 122
    Points : 356
    Points
    356
    Par défaut
    parce que -1 + -1 + 0 = -2 ≠ 0 …

  7. #7
    Membre du Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    février 2021
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Meurthe et Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Boutique - Magasin

    Informations forums :
    Inscription : février 2021
    Messages : 25
    Points : 46
    Points
    46
    Par défaut
    Citation Envoyé par WhiteCrow Voir le message
    parce que -1 + -1 + 0 = -2 ≠ 0 …
    je me suis trompé

    voila mon output pour l'instant :

    [[-1,0,1],[-1,1,0],[-1,2,-1],[-1,-1,2],[0,-1,1],[0,1,-1],[0,1,-1],[0,-1,1],[1,-1,0],[1,0,-1],[1,0,-1],[1,-1,0],[2,-1,-1],[2,-1,-1],[-1,-1,2],[-1,0,1],[-1,1,0],[-1,2,-1]]


    ils font tous 0 mais seulement deux sont bon , pk ? s'il vous plais

  8. #8
    Membre averti
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    122
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 122
    Points : 356
    Points
    356
    Par défaut
    parce que tu as des doublons
    [-1,0,1] c'est la même chose que [-1,1,0] ou [0,-1,1], [0,1,-1], [1,0,-1], [1,-1,0] , …
    et surtout [-1,0,1] c'est le même que tu prennes le premier -1 du tableau ou le second …

  9. #9
    Membre du Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    février 2021
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Meurthe et Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Boutique - Magasin

    Informations forums :
    Inscription : février 2021
    Messages : 25
    Points : 46
    Points
    46
    Par défaut
    J'ai réussi ! j'ai remarqué que les solutions étaient des tableaux où les valeurs sont dans l'ordre, j'ai donc ordonné les triplets ça m'a donné plein de doublons et j'ai dédoublonné avec array_unique qui marche sur les tableau de tableau ( ouf ) et le output à été accepté , j'attend de comprendre bien l'énoncé avant de mettre résolu.

    Je fait appel à une personne pédagogue , à votre bon cœur.

    je met mon code , il n'est pas beau , il à une complexité de en n3 etc .. je sais

    merci de tout aide cordialement
    Code php : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    function threeSum($nums) {
     
           $o =0 ;
     
           for ($i=0;$i<count($nums);$i++){          
              for ($j=0;$j<count($nums);$j++){             
                   for ($k=0;$k<count($nums);$k++){                      
     
                         if ($k != $j && $i != $j && $k !=  $i){                        
     
                            if ($nums[$i] + $nums[$j] + $nums[$k] === 0){                          
     
                             $tab[0] = $nums[$i];
                             $tab[1] = $nums[$j];
                             $tab[2] = $nums[$k];                        
     
                             sort($tab);                         
     
                             $res[$o] = [ $tab[0],$tab[1],$tab[2] ] ;
     
                             $o++;           
     
                         }
                       }
     
     
                  }
               }
             } 
     
     
          return array_unique($res,SORT_REGULAR);  
     
        }
    }

    maintenant la dernière étape c'est de retourner [] si le input est [0] ou [] ,

    la condition que j'ai écrite est

    Code php : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    if( ( ! empty($nums) ) || !(  (count($num) == 1 ) &&    ($num[0] == 0) )  ){   
     
     
    //faire le traitement
     
    }else{
     
     
    // retourner []
     
    }

    mais j'ai une erreur quand le input est []

    des lanternes ?

  10. #10
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 684
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 684
    Points : 11 751
    Points
    11 751
    Par défaut
    Bonjour

    Sans vouloir être désagréable, c'est ce code qui ne va pas :
    Code php : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    for ($i=0;$i<count($nums);$i++){
    for ($j=0;$j<count($nums);$j++){
    for ($k=0;$k<count($nums);$k++){

    On préférera :

    Code php : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    for ($i=0;$i<count($nums);$i++){
    for ($j=$i+1;$j<count($nums);$j++){
    for ($k=$j+1;$k<count($nums);$k++){

    Cette version rend inutile la condition qui suit (de différence des indices), et le dédoublonnage.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  11. #11
    Membre averti
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    122
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 122
    Points : 356
    Points
    356
    Par défaut
    Citation Envoyé par Flodelarab Voir le message
    [...]

    Cette version rend inutile la condition qui suit (de différence des indices), et le dédoublonnage.
    Attention aux cas comme [-1, -1, -1, 2] qui malgré les nouvelles initialisations de boucles donneront des doublons …

  12. #12
    Membre du Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    février 2021
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Meurthe et Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Boutique - Magasin

    Informations forums :
    Inscription : février 2021
    Messages : 25
    Points : 46
    Points
    46
    Par défaut
    merci je vais tester tout ça


  13. #13
    Membre du Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    février 2021
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Meurthe et Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Boutique - Magasin

    Informations forums :
    Inscription : février 2021
    Messages : 25
    Points : 46
    Points
    46
    Par défaut
    Citation Envoyé par Flodelarab Voir le message
    Bonjour

    Sans vouloir être désagréable, c'est ce code qui ne va pas :
    Code php : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    for ($i=0;$i<count($nums);$i++){
    for ($j=0;$j<count($nums);$j++){
    for ($k=0;$k<count($nums);$k++){

    On préférera :

    Code php : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    for ($i=0;$i<count($nums);$i++){
    for ($j=$i+1;$j<count($nums);$j++){
    for ($k=$j+1;$k<count($nums);$k++){

    Cette version rend inutile la condition qui suit (de différence des indices), et le dédoublonnage.
    salut , j'avais pensé à ça au début mais j'aime bien faire compliqué lol

    tu veux dire comme ça ?

    Code php : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    function threeSum($nums) {               
     
          for ($i=0;$i<count($nums);$i++){
          for ($j=$i+1;$j<count($nums);$j++){
          for ($k=$j+1;$k<count($nums);$k++){               
     
                         if ($nums[$i] + $nums[$j] + $nums[$k] === 0){                                
     
    $tab[0] = $nums[$i];
    $tab[1] = $nums[$j];
    $tab[2] = $nums[$k];
     
    sort($tab);
     
    $res[$o] = [ $tab[0],$tab[1],$tab[2] ] ;
     
    $o++;                 
                         }
     
     
     
           }}} 
     
     
     
          return $res;    
     
     
        }
    }


    mais ça retourne un doublon quand même , peut tu me dire pk ?
    une condition qui manque ?

  14. #14
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 684
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 684
    Points : 11 751
    Points
    11 751
    Par défaut
    Citation Envoyé par WhiteCrow Voir le message
    Attention aux cas comme [-1, -1, -1, 2] qui malgré les nouvelles initialisations de boucles donneront des doublons …
    Tu as raison sur le fait que le dédoublonnage est quand même nécessaire. Par contre, ton exemple n'est pas bon. Il y a plusieurs [-1;0;1], mais il y a un seul [-1, -1, 0, 2]. Quant à [-1, -1, -1, 2], la somme ne fait pas 0.

    Citation Envoyé par serpentcorail Voir le message
    mais ça retourne un doublon quand même , peut tu me dire pk ?
    Car -1 est présent 2 fois dans ton tableau. Empêcher les doublons d'indices n'empêche pas les doublons de valeurs.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  15. #15
    Membre averti
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    122
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 122
    Points : 356
    Points
    356
    Par défaut
    Citation Envoyé par Flodelarab Voir le message
    Tu as raison sur le fait que le dédoublonnage est quand même nécessaire. Par contre, ton exemple n'est pas bon. Il y a plusieurs [-1;0;1], mais il y a un seul [-1, -1, 0, 2]. Quant à [-1, -1, -1, 2], la somme ne fait pas 0.
    [-1, -1, -1, 2] est le tableau de départ pas un résultat ; ton algo produit comme résultat [ [-1,-1,2],[-1,-1,2] ]
    Une de mes idées de départ (la seconde) était en fait de non seulement trier le tableau d'origine mais de ne garder au maximum que 2 exemplaire de chaque nombre (avec le cas du triple 0 qui convient comme solution et qu'il faut traiter à part). Le tri en n×log n, le filtrage en n et la recherche en n² donne un bon algo avec un complexité spatiale en n tout de même … je pense qu'on peut réduire cette complexité spatiale en O(1) …

  16. #16
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 684
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 684
    Points : 11 751
    Points
    11 751
    Par défaut
    Citation Envoyé par WhiteCrow Voir le message
    [-1, -1, -1, 2] est le tableau de départ pas un résultat ; ton algo produit comme résultat [ [-1,-1,2],[-1,-1,2] ]
    Et non. Toujours pas. Car pour obtenir 2 fois [-1,-1,2], il faudrait tirer 2 fois les indices 0, 3 et 4, ce qui est impossible.
    Le bon contre-exemple est bien celui que j'ai donné : [-1, 0,1]. Car comme il y a 2 valeurs -1, on ne peut pas éviter le tirage des indices (0;1;2) et (1;2;4). C'est là que le doublon apparaît.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  17. #17
    Membre du Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    février 2021
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Meurthe et Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Boutique - Magasin

    Informations forums :
    Inscription : février 2021
    Messages : 25
    Points : 46
    Points
    46
    Par défaut
    Example 1:

    Input: nums = [-1,0,1,2,-1,-4]
    Output: [[-1,-1,2],[-1,0,1]]
    Example 2:

    Input: nums = []
    Output: []
    Example 3:

    Input: nums = [0]
    Output: []



    maintenant ça bloque pour le deuxième cas si le tableau est vide je fais un return []; mais le site le rejette , j'obtiens une erreur comme si le type attendu ne correspondais pas

  18. #18
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 684
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 684
    Points : 11 751
    Points
    11 751
    Par défaut
    Quel langage de programmation ?
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  19. #19
    Membre averti
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    122
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 122
    Points : 356
    Points
    356
    Par défaut
    Citation Envoyé par Flodelarab Voir le message
    Citation Envoyé par WhiteCrow Voir le message
    [-1, -1, -1, 2] est le tableau de départ pas un résultat ; ton algo produit comme résultat [ [-1,-1,2],[-1,-1,2] ]
    Et non. Toujours pas. Car pour obtenir 2 fois [-1,-1,2], il faudrait tirer 2 fois les indices 0, 3 et 4, ce qui est impossible.
    Le bon contre-exemple est bien celui que j'ai donné : [-1, 0,1]. Car comme il y a 2 valeurs -1, on ne peut pas éviter le tirage des indices (0;1;2) et (1;2;4). C'est là que le doublon apparaît.
    Bon je vais parler plus simplement :

    A=[-1, -1, -1, 2 ]
    i=0, j=1, k=2 → [-1, -1, -1] → Σ=-3 pas une solution
    i=0, j=1, k=3 → [-1, -1, 2] → Σ=0 une solution !
    i=1, j=2, k=3 → [-1, -1, 2] → Σ=0 une solution mais en double … avec des éléments qui n'ont pas les même indices …

  20. #20
    Membre du Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    février 2021
    Messages
    25
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Meurthe et Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Boutique - Magasin

    Informations forums :
    Inscription : février 2021
    Messages : 25
    Points : 46
    Points
    46
    Par défaut
    Citation Envoyé par Flodelarab Voir le message
    Quel langage de programmation ?
    C'est le même test de début du post , c'est en PHP , quand le input est [] ou [0] ça doit retourner [] c'est un tableau nulle je suppose un var_dump donne NULL , mais le compilo, je veux dire l'interpréteur , pardon, de de Leetcode me refuse ça

Discussions similaires

  1. [V6] Synchronisation incompréhensible (pour moi)
    Par TomDuBouchon dans le forum Designer
    Réponses: 5
    Dernier message: 12/08/2009, 15h52
  2. Xcode - erreur incompréhensible (pour moi ^^)
    Par JeeWee dans le forum Autres éditeurs
    Réponses: 3
    Dernier message: 08/12/2008, 13h33
  3. Réponses: 4
    Dernier message: 07/04/2006, 16h30

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo