Practice #5
Leçon 14 sur 14 du cours Liste doublement chaînée - Série Structures de données n°6 de Coddy.
Défi
FacileÉtant donné un tableau d'entiers trié arr (les valeurs d'une liste doublement chaînée triée) et un entier target, écrivez une fonction countPairs qui renvoie le nombre de paires d'indices (i, j) avec i < j et arr[i] + arr[j] == target.
Supposez que l'entrée ne contient aucune valeur en double.
Utilisez une liste doublement chaînée pour résoudre ce problème ! Deux pointeurs partant des deux extrémités, se déplaçant vers l'intérieur.
Vous devez utiliser la classe DoublyLinkedList (fournie dans doublylinkedlist.<ext> ainsi que node.<ext>) — n'utilisez pas les fonctions intégrées du langage comme l'inversion de tableaux, le découpage (slicing), le tri ou les opérations de liste de la bibliothèque standard pour calculer le résultat.
Essayez vous-même
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char line1[8192];
char line2[64];
if (!fgets(line1, sizeof(line1), stdin)) line1[0] = '\0';
if (!fgets(line2, sizeof(line2), stdin)) line2[0] = '\0';
int arr[4096];
int len = 0;
char* tok = strtok(line1, " \t\r\n");
while (tok) { arr[len++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
int n = atoi(line2);
int r = countPairs(arr, len, n);
printf("%d\n", r);
return 0;
}
