เราได้รับลิงก์ลิสต์สองตัวและงานคือการสร้างคู่โดยใช้องค์ประกอบจำนวนเต็มของลิงก์ลิสต์ให้ผลรวมเท่ากับค่าที่กำหนดสมมติว่า k ลิงก์ลิสต์คือลำดับของโครงสร้างข้อมูลที่เชื่อมต่อกันผ่านลิงก์
อินพุต
vector v_1 = {5, 7, 8, 10, 11},. vector v_2 = {6, 4, 3, 2, 0} , int k = 11เอาต์พุต
Count of pairs from two linked lists whose sum is equal to a given value k are: 4
คำอธิบาย
คู่ที่สามารถสร้างได้จากลิงก์ลิสต์ที่กำหนดคือ: (5, 6) = 11(เท่ากับ k), (5, 4) = 9(ไม่เท่ากับ k), (5, 3) = 8(ไม่เท่ากับ k), (5, 2) = 7(ไม่เท่ากับ k), (5, 0) = 5(ไม่เท่ากับ k), (7, 6) = 13(ไม่เท่ากับ k), (7, 4) = 11(เท่ากับ k), (7, 3) = 10(ไม่เท่ากับ k), (7, 2) = 9(ไม่เท่ากับ k), (7, 0) = 7(ไม่เท่ากับ k), (8, 6) = 14(ไม่เท่ากับ k), (8, 4) = 12(ไม่เท่ากับ k), (8, 3) = 11(เท่ากับ k), (8, 2) = 10(ไม่เท่ากับ k), (8, 0) = 8(ไม่เท่ากับ k), (10, 6) = 16(ไม่เท่ากับ k), (10, 4) = 14(ไม่เท่ากับ k), (10, 3) = 13(ไม่เท่ากับ k), (10, 2) = 12(ไม่เท่ากับ k), (10, 0) = 10(ไม่เท่ากับ k), (11, 6) = 17(ไม่เท่ากับ k), (11, 4) = 15(ไม่เท่ากับ k), (11, 3) = 14(ไม่เท่ากับ k), (11, 2) = 13(ไม่เท่ากับ k), (11, 0) = 11(ไม่เท่ากับ k) ดังนั้นชัดเจนว่ามี 3 คู่ที่เท่ากับผลรวมที่กำหนด
อินพุต
vector v_1 = {2, 3, 5, 6},. vector v_2 = {6, 4, 3} , int k = 6เอาต์พุต
Count of pairs from two linked lists whose sum is equal to a given value k are: 2
คำอธิบาย
คู่ที่สามารถสร้างได้จากลิงก์ลิสต์ที่กำหนดคือ: (2, 6) = 8(ไม่เท่ากับ k), (2, 4) = 6(เท่ากับ k), (2, 3) = 5(ไม่เท่ากับ k), (3, 6) = 9(ไม่เท่ากับ k), (3, 4) = 7(ไม่เท่ากับ k), (3, 3) = 6(เท่ากับ k), (5, 6) = 11(ไม่เท่ากับ k), (5, 4) = 9(ไม่เท่ากับ k), (5, 3) = 8(ไม่เท่ากับ k), (6, 6) = 12(ไม่เท่ากับ k), (6, 4) = 10(ไม่เท่ากับ k), (6, 3) = 9(ไม่เท่ากับ k) ดังนั้นชัดเจนว่ามี 2 คู่ที่เท่ากับผลรวมที่กำหนด
วิธีการที่ใช้ในโปรแกรมด้านล่าง
รับค่า k และค่าจำนวนเต็มลงในสองเวกเตอร์เพื่อสร้างลิงก์ลิสต์
สร้างฟังก์ชันที่จะสร้างลิงก์ลิสต์โดยใช้เวกเตอร์ที่ส่งเป็นอาร์กิวเมนต์
ท่องลูปจนถึงขนาดของเวกเตอร์และสร้างอ็อบเจกต์พอยน์เตอร์ของคลาส ListNode
ท่องลูป while ptr->next ไม่เท่ากับ NULL และตั้ง ptr เป็น ptr->next
ภายใน ptr->next ตั้ง vector[i]
คืนค่า start
สร้างฟังก์ชันที่จะคืนค่าจำนวนคู่ที่ตรงกับผลรวมที่กำหนด
ใช้ตัวแปรชั่วคราว count ตั้งเป็น 0
สร้างอ็อบเจกต์พอยน์เตอร์สองตัวคือ *first_list สำหรับลิงก์ลิสต์แรกและ *second_list สำหรับลิงก์ลิสต์ที่สอง
เริ่มลูปจากพอยน์เตอร์เริ่มต้นของลิสต์แรกจนลิสต์ไม่ว่าง
ภายในลูป เริ่มลูปอีกอันจากพอยน์เตอร์เริ่มต้นของลิสต์ที่สองจนลิสต์ไม่ว่าง
ภายในลูป ตรวจสอบ IF (first_list->data + second_list->data) == k แล้วเพิ่ม count ขึ้น 1
คืนค่า count
พิมพ์ผลลัพธ์
ตัวอย่าง
#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); }เอาต์พุต
ถ้าเรารันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −
Count of pairs from two linked lists whose sum is equal to a given value k are: 4
