Practice #5
Lektion 14 von 14 im Kurs Doppelt verkettete Liste - Datenstrukturen-Serie #6 von Coddy.
Aufgabe
EinfachGegeben ist ein sortiertes Ganzzahl-Array arr (die Werte einer sortierten doppelt verketteten Liste) und eine Ganzzahl target. Schreiben Sie eine Funktion countPairs, die die Anzahl der Paare von Indizes (i, j) mit i < j und arr[i] + arr[j] == target zurückgibt.
Gehen Sie davon aus, dass die Eingabe keine doppelten Werte enthält.
Verwenden Sie eine doppelt verkettete Liste, um dieses Problem zu lösen! Zwei Pointer von beiden Enden, die sich nach innen bewegen.
Sie müssen die Klasse DoublyLinkedList verwenden (bereitgestellt in doublylinkedlist.<ext> zusammen mit node.<ext>) — verwenden Sie keine in der Sprache eingebauten Funktionen wie Array-Reverse, Slicing, Sortierung oder Standardbibliotheks-Listenoperationen, um das Ergebnis zu berechnen.
Probier es selbst
#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;
}
