Chúng tôi được cung cấp với hai danh sách được liên kết và nhiệm vụ là tạo các cặp bằng cách sử dụng các phần tử nguyên của danh sách được liên kết sao cho tổng của chúng bằng một giá trị đã cho, giả sử là k. Danh sách được liên kết là một chuỗi các cấu trúc dữ liệu, được kết nối với nhau thông qua các liên kết.
Đầu vào
vector v_1 = {5, 7, 8, 10, 11},.
vector v_2 = {6, 4, 3, 2, 0} , int k = 11 Đầu ra
Count of pairs from two linked lists whose sum is equal to a given value k are: 4
Giải thích
The pairs which can be formed using the given linked lists are: (5, 6) = 11(equals to k), (5, 4) = 9(not equals to k), (5, 3) = 8(not equals to k), (5, 2) = 7(not equals to k), (5, 0) = 5(not equals to k), (7, 6) = 13(not equals to k), (7, 4) = 11(equals to k), (7, 3) = 10(not equals to k), (7, 2) = 9(not equals to k), (7, 0) = 7(not equals to k), (8, 6) = 14(not equals to k), (8, 4) = 12(not equals to k), (8, 3) = 11(equals to k), (8, 2) = 10(not equals to k), (8, 0) = 8(not equals to k), (10, 6) = 16(not equals to k), (10, 4) = 14(not equals to k), (10, 3) = 13(not equals to k), (10, 2) = 12(not equals to k), (10, 0) = 10(not equals to k), (11, 6) = 17(not equals to k), (11, 4) = 15(not equals to k), (11, 3) = 14(not equals to k), (11, 2) = 13(not equals to k), (11, 0) = 11(not equals to k). So, clearly there are 3 pairs which are equal to the given sum.
Đầu vào
vector v_1 = {2, 3, 5, 6},.
vector v_2 = {6, 4, 3} , int k = 6 Đầu ra
Count of pairs from two linked lists whose sum is equal to a given value k are: 2
Giải thích
The pairs which can be formed using the given linked lists are: (2, 6) = 8(not equals to k), (2, 4) = 6(equals to k), (2, 3) = 5(not equals to k), (3, 6) = 9(not equals to k), (3, 4) = 7(not equals to k), (3, 3) = 6(equals to k), (5, 6) = 11(not equals to k), (5, 4) = 9(not equals to k), (5, 3) = 8(not equals to k), (6, 6) = 12(not equals to k), (6, 4) = 10(not equals to k), (6, 3) = 9(not equals to k),. So, clearly there are 2 pairs which are equal to the given sum.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Nhập giá trị của k và giá trị kiểu số nguyên vào hai vectơ để chúng ta có thể chuyển các vectơ để tạo thành danh sách liên kết
-
Tạo một hàm sẽ tạo danh sách được liên kết bằng cách sử dụng vectơ được truyền làm đối số cho hàm.
-
Di chuyển vòng lặp cho đến hết kích thước của một vectơ và tạo một đối tượng con trỏ của lớp
Mã danh sách
-
Duyệt qua vòng lặp trong khi ptr-> tiếp theo không bằng NULL và đặt ptr thành ptr-> tiếp theo
-
Bên trong ptr-> vectơ tập hợp tiếp theo [i]
-
Bắt đầu trở lại
-
-
Tạo một hàm sẽ trả về số lượng các cặp khớp với tổng đã cho.
-
Lấy một số lượng biến tạm thời và đặt nó thành 0
-
Tạo hai đối tượng con trỏ, tức là * first_list cho danh sách được liên kết đầu tiên và * second_list cho danh sách được liên kết thứ hai.
-
Vòng lặp bắt đầu từ con trỏ bắt đầu của danh sách đầu tiên cho đến khi danh sách không trống
-
Bên trong vòng lặp, bắt đầu một vòng lặp khác từ con trỏ bắt đầu của danh sách thứ hai cho đến khi danh sách không trống
-
Bên trong vòng lặp, kiểm tra IF (first_list-> data + second_list-> data) ==k sau đó tăng số lượng lên 1
-
Trả lại số lượng
-
-
In kết quả.
Ví dụ
#include<bits/stdc++.h>
using namespace std;
class ListNode{
public:
int data;
ListNode *next;
ListNode(int data){
this->data = data;
next = NULL;
}
};
ListNode *CreateList(vector v){
ListNode *start = new ListNode(v[0]);
for (int i = 1; i < v.size(); i++){
ListNode *ptr = start;
while (ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return start;
}
int sum_pair(ListNode *start_1, ListNode *start_2, int k){
int count = 0;
ListNode *first_list , *second_list;
for (first_list = start_1; first_list != NULL; first_list = first_list->next){
for (second_list = start_2; second_list != NULL; second_list = second_list->next){
if ((first_list->data + second_list->data) == k){
count++;
}
}
}
return count;
}
int main(){
vector<int> v_1 = {5, 7, 8, 10, 11};
ListNode* start_1 = CreateList(v_1);
vector v_2 = {6, 4, 3, 2, 0};
ListNode* start_2 = CreateList(v_2);
int k = 11;
cout<<"Count of pairs from two linked lists whose sum is equal to a given value k are: "<<sum_pair(start_1, start_2, k);
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of pairs from two linked lists whose sum is equal to a given value k are: 4