นับคู่จากลิงก์ลิสต์สองตัวที่ผลคูณเท่ากับค่าที่กำหนดใน C++

เราได้รับลิงก์ลิสต์สองตัวและงานคือการสร้างคู่โดยใช้องค์ประกอบจำนวนเต็มของลิงก์ลิสต์ให้ผลคูณเท่ากับค่าที่กำหนดสมมติว่า k ลิงก์ลิสต์คือลำดับของโครงสร้างข้อมูลที่เชื่อมต่อกันผ่านลิงก์

อินพุต

vector v_1 = {5, 7, 8, 10, 11},. vector v_2 = {6, 4, 3, 2, 0} , int k = 20

เอาต์พุต

Count of pairs from two linked lists whose product is equal to a given value k are: 2

คำอธิบาย

คู่ที่สามารถสร้างได้จากลิงก์ลิสต์ที่กำหนดคือ: (5, 6) = 30(ไม่เท่ากับ k), (5, 4) = 20(เท่ากับ k), (5, 3) = 15(ไม่เท่ากับ k), (5, 2) = 10(ไม่เท่ากับ k), (5, 0) = 0(ไม่เท่ากับ k), (7, 6) = 42(ไม่เท่ากับ k), (7, 4) = 28(ไม่เท่ากับ k), (7, 3) = 21(ไม่เท่ากับ k), (7, 2) = 14(ไม่เท่ากับ k), (7, 0) = 0(ไม่เท่ากับ k), (8, 6) = 48(ไม่เท่ากับ k), (8, 4) = 32(ไม่เท่ากับ k), (8, 3) = 24(ไม่เท่ากับ k), (8, 2) = 16(ไม่เท่ากับ k), (8, 0) = 0(ไม่เท่ากับ k), (10, 6) = 60(ไม่เท่ากับ k), (10, 4) = 40(ไม่เท่ากับ k), (10, 3) = 30(ไม่เท่ากับ k), (10, 2) = 20(ไม่เท่ากับ k), (10, 0) = 0(ไม่เท่ากับ k), (11, 6) = 66(ไม่เท่ากับ k), (11, 4) = 44(ไม่เท่ากับ k), (11, 3) = 3(ไม่เท่ากับ k), (11, 2) = 22(ไม่เท่ากับ k), (11, 0) = 0(ไม่เท่ากับ k) ดังนั้นชัดเจนว่ามี 2 คู่ที่เท่ากับผลคูณที่กำหนด

อินพุต

vector v_1 = {2, 3, 5, 6},. vector v_2 = {6, 4, 3} , int k = 9

เอาต์พุต

Count of pairs from two linked lists whose sum is equal to a given value k are: 1

คำอธิบาย

คู่ที่สามารถสร้างได้จากลิงก์ลิสต์ที่กำหนดคือ: (2, 6) = 12(ไม่เท่ากับ k), (2, 4) = 8(ไม่เท่ากับ k), (2, 3) = 6(ไม่เท่ากับ k), (3, 6) = 18(ไม่เท่ากับ k), (3, 4) = 12(ไม่เท่ากับ k), (3, 3) = 9(เท่ากับ k), (5, 6) = 30(ไม่เท่ากับ k), (5, 4) = 20(ไม่เท่ากับ k), (5, 3) = 15(ไม่เท่ากับ k), (6, 6) = 36(ไม่เท่ากับ k), (6, 4) = 24(ไม่เท่ากับ k), (6, 3) = 18(ไม่เท่ากับ k) ดังนั้นชัดเจนว่ามี 1 คู่ที่เท่ากับผลรวมที่กำหนด

วิธีการที่ใช้ในโปรแกรมด้านล่าง

• รับค่า 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 product_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 = 30;    cout<<"Count of pairs from two linked lists whose product is equal to a given value k are: "<<product_pair(start_1, start_2, k); }

เอาต์พุต

ถ้าเรารันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −

Count of pairs from two linked lists whose product is equal to a given value k are: 2