นับคู่จากสองรายการที่เชื่อมโยงซึ่งผลรวมเท่ากับค่าที่กำหนดใน C++

เรามีรายการที่เชื่อมโยงสองรายการและงานคือการสร้างคู่โดยใช้องค์ประกอบจำนวนเต็มของรายการที่เชื่อมโยงเพื่อให้ผลรวมของพวกเขาเท่ากับค่าที่กำหนดซึ่งก็คือ 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

คำอธิบาย

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.

ป้อนข้อมูล

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

คำอธิบาย

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.

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

• ป้อนค่าของ k และค่าประเภทจำนวนเต็มลงในเวกเตอร์สองตัว เพื่อให้เราสามารถส่งเวกเตอร์เพื่อสร้างรายการที่เชื่อมโยงได้

• สร้างฟังก์ชันที่จะสร้างรายการเชื่อมโยงโดยใช้เวกเตอร์ที่ส่งผ่านเป็นอาร์กิวเมนต์ไปยังฟังก์ชัน

• สำรวจลูปจนถึงขนาดของเวกเตอร์และสร้างวัตถุตัวชี้ของคลาส

  ListNode

  • ข้ามลูปในขณะที่ ptr-> next ไม่เท่ากับ NULL และตั้งค่า ptr เป็น ptr->next

  • ภายใน ptr->ชุดถัดไป vector[i]

  • จุดเริ่มต้นกลับ

• สร้างฟังก์ชันที่จะคืนค่าจำนวนคู่ที่ตรงกับผลรวมที่กำหนด

  • นับตัวแปรชั่วคราวแล้วตั้งค่าเป็น 0

  • สร้างวัตถุตัวชี้สองตัว เช่น *first_list สำหรับรายการที่เชื่อมโยงรายการแรก และ *second_list สำหรับรายการที่เชื่อมโยงที่สอง

  • เริ่มวนซ้ำจากตัวชี้เริ่มต้นของรายการแรกจนถึงรายการไม่ว่างเปล่า

  • ภายในลูป เริ่มลูปใหม่จากตัวชี้เริ่มต้นของรายการที่สอง จนกว่ารายการจะไม่ว่าง

  • ภายในลูป ให้ตรวจสอบ IF (first_list->data + second_list->data) ==k จากนั้นเพิ่มจำนวนขึ้น 1

  • คืนจำนวน

• พิมพ์ผลลัพธ์

ตัวอย่าง

#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