Luyện tập #5
Bài học 14 trên 14 trong khóa học Danh sách liên kết kép, chuỗi cấu trúc dữ liệu #6 của Coddy.
Thử thách
DễCho một mảng số nguyên đã sắp xếp arr (các giá trị của một danh sách liên kết đôi đã sắp xếp) và một số nguyên target, hãy viết hàm countPairs trả về số cặp chỉ số (i, j) thỏa mãn i < j và arr[i] + arr[j] == target.
Giả sử đầu vào không có giá trị trùng lặp.
Hãy dùng danh sách liên kết đôi để giải bài toán này! Dùng hai con trỏ từ hai đầu và di chuyển vào trong.
Bạn phải dùng lớp DoublyLinkedList (được cung cấp trong doublylinkedlist.<ext> cùng với node.<ext>) , không dùng các thao tác có sẵn trong ngôn ngữ như đảo ngược mảng, cắt lát, sắp xếp hoặc các thao tác trên danh sách của thư viện chuẩn để tính kết quả.
Tự làm thử
#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;
}
Tất cả bài học trong Danh sách liên kết kép, chuỗi cấu trúc dữ liệu #6
Tự luyện tập: Trình biên dịch C online