Đếm bộ ba trong danh sách liên kết đôi đã sắp xếp có tổng bằng x trong C++

Cho một danh sách liên kết đôi đã sắp xếp chứa các giá trị nguyên. Mục tiêu là tìm các bộ ba có tổng bằng giá trị x cho trước. Nếu danh sách liên kết đầu vào là 3-4-1-2 và x là 6 thì số lượng sẽ là 1 (bộ ba (3,1,2)).

Ví dụ

Đầu vào

danh sách liên kết: [3-4-13-5-10-10-0] x=20

Đầu ra

Số bộ ba trong danh sách liên kết đôi đã sắp xếp có tổng bằng x là: 2

Giải thích

Các bộ ba sẽ là: (3,4,13) và (10,10,0)

Đầu vào

danh sách liên kết: [4-3-1-5-2-4-2] x=8

Đầu ra

Số bộ ba trong danh sách liên kết đôi đã sắp xếp có tổng bằng x là: 6

Giải thích

Các bộ ba sẽ là: (4,3,1), (1,5,2), (3,1,4), (1,5,2), (4,2,2) và (2,4,2)

Phương pháp sử dụng

Trong phương pháp này:

• Chúng ta lấy nút danh sách liên kết là struct chứa phần dữ liệu int data và con trỏ tự tham chiếu next và previous.
• Hàm insert_node(struct block** head, int data) thêm nút vào đầu danh sách liên kết với dữ liệu.
• Hàm sum_x(struct block* head, int x) nhận con trỏ đến đầu danh sách liên kết đôi và số nguyên x và trả về số bộ ba các nút có tổng phần dữ liệu bằng x.
• Khởi tạo biến đếm ban đầu là 0.
• Lấy ba con trỏ temp_1, temp_2 và temp_3 kiểu struct block.
• Bắt đầu từ temp_1 trỏ đến đầu danh sách liên kết, temp_2 trỏ đến kế tiếp temp_1 và temp_3 trỏ đến kế tiếp temp_2, ta có ba con trỏ trỏ đến ba nút đầu tiên.
• Duyệt bằng các con trỏ này cho đến nút cuối cùng.
• Nếu phần dữ liệu hiện tại của tất cả các con trỏ trên có tổng bằng x ((temp_1->data + temp_2->data + temp_3->data) == x) thì tăng biến đếm.
• Cuối cùng, chúng ta đếm được số bộ ba và lưu trong biến đếm.
• Trả về biến đếm làm kết quả.

Ví dụ mã

#include <iostream> 
using namespace std; 

struct block {
    int data;
    struct block *next, *prev;
};

void insert_node(struct block** head, int data) {
    struct block* ptr = new block();
    ptr->data = data;
    ptr->next = NULL;
    ptr->prev = NULL;
    
    if ((*head) == NULL) {
        (*head) = ptr;
    } else {
        ptr->next = *head;
        (*head)->prev = ptr;
        (*head) = ptr;
    }
}

int sum_x(struct block* head, int x) {
    int count = 0;
    struct block *temp_1, *temp_2, *temp_3;
    
    for (temp_1 = head; temp_1 != NULL; temp_1 = temp_1->next) {
        for (temp_2 = temp_1->next; temp_2 != NULL; temp_2 = temp_2->next) {
            for (temp_3 = temp_2->next; temp_3 != NULL; temp_3 = temp_3->next) {
                if ((temp_1->data + temp_2->data + temp_3->data) == x) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

int main() {
    struct block* head = NULL;
    insert_node(&head, 200);
    insert_node(&head, 100);
    insert_node(&head, 16);
    insert_node(&head, 14);
    insert_node(&head, 10);
    insert_node(&head, 10);
    insert_node(&head, 2);
    int x = 22;
    cout << "Số bộ ba trong danh sách liên kết đôi đã sắp xếp có tổng bằng x là: " << sum_x(head, x);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số bộ ba trong danh sách liên kết đôi đã sắp xếp có tổng bằng x là: 1