جفت ها را از دو لیست پیوند خورده که مجموع آنها برابر با یک مقدار مشخص است ، بشمارید


سطح دشواری متوسط
اغلب در خشت آمازون Avalara Expedia متعصبان گوگل در واقع مایکروسافت پی پال تسلا
هشی کردن لینک شده مرتب سازی

بیان مسأله

مسئله "جفت ها را از دو لیست پیوند خورده که مجموع آنها برابر با یک مقدار معین است" شمرد و بیان می کند که به شما دو لیست پیوندی و یک مقدار عدد صحیح داده می شود. از عبارت مسئله خواسته شد تا دریابد که چند کل جفت جمع برابر با مقدار داده شده است.

مثال

LinkedList1 = 11 à 6 à 1 à 8

LinkedList2 = 5 à 3 à 1 à 9

Sum = 9
2

توضیح: دو جفت وجود دارد ، یعنی 6 ، 3 و 8 ، 1 که مقدار را به مقدار داده شده 9 جمع می کند.

 

الگوریتم برای شمارش جفتهایی از لیستهای پیوندی که مجموع آنها برابر با یک مقدار مشخص است

1. Push all the integer values to the two different linked lists.
2. Declare a set.
3. Set the count to 0.
4. Iterate over the first linked list and put all the values of it into the linked list1.
5. Iterate over the second linked list
    1. Check if the set contains the difference between the value of x and a current element of linked list2.
        1. If true then increase the value of count by 1.
6. Return count.

توضیح

مقادیر صحیح به عنوان ورودی به ما داده می شود. بنابراین ، همه آنها را به لیست های پیوندی هدایت خواهیم کرد. در C ++ ، ما برای اجرای این راه حل خارجی روش پیاده سازی یک لیست پیوندی ایجاد کرده ایم. اما در جاوا ، ما یک کلاس ساخته شده از Linked List داریم که به کمک آن می توانیم همه مقادیر عدد صحیح را به راحتی در لیست پیوند دهیم. اکنون ما خواسته ایم که این جفت را در هر دو لیست پیوند یافته پیدا کنیم که تعداد آنها به مقدار داده شده می رسد.

ما می خواهیم تمام مقادیر عدد صحیح را به لیست پیوند داده شده هدایت کنیم. ما قصد استفاده از تنظیم ساختار داده است و تمام مقادیر پیوند لیست 1 را رد می کند و تمام مقادیر لیست پیوند داده شده برای اولین بار را ذخیره می کند. Set همچنین یک ویژگی فراهم می کند که عناصر مشترک به طور خودکار از مجموعه حذف می شوند. بنابراین اگر دفعه دیگر از مجموعه استفاده کنیم ، هیچ مشکلی برای عناصر مشترک وجود ندارد و همچنین هیچ یک از عناصر مشترک موجود در لیست پیوندی وجود نخواهد داشت.

اکنون تمام مقادیر موجود در لیست پیوندی 1 را در مجموعه داریم. اکنون لیست پیوند داده شده دوم را رد می کنیم و بررسی می کنیم که آیا تفاوت بین x و هر مقدار از لیست دوم در مجموعه وجود دارد یا خیر. اگر در حال حاضر باشد ، اکنون یک جفت پیدا کرده ایم و همچنین مقدار شمارش را 1 افزایش خواهیم داد. این بدان معنی است که 1 جفت پیدا شده و شمارش می شود. در پایان پیمایش. مقدار شمارش تعداد جفتی خواهد بود که مجموع آن برابر با مقدار داده شده باشد.

جفت ها را از دو لیست پیوند خورده که مجموع آنها برابر با یک مقدار مشخص است ، بشمارید

رمز

C ++ برای شمارش جفت از دو لیست پیوند یافته که مجموع آنها برابر با یک مقدار مشخص است

#include<iostream>
#include<unordered_set>

using namespace std;

struct Node
{
    int data;
    struct Node* next;
};

void implementLinkedList(struct Node** headReference, int newItem)
{
    struct Node* newNode =	(struct Node*) malloc(sizeof(struct Node));

    newNode->data = newItem;

    newNode->next = (*headReference);

    (*headReference) = newNode;
}
int getPairOfsum (struct Node* head1, struct Node* head2,int sum)
{
    int count = 0;

    unordered_set<int> SET;

    while (head1 != NULL)
    {
        SET.insert(head1->data);

        head1 = head1->next;
    }

    while (head2 != NULL)
    {
        if (SET.find(sum - head2->data) != SET.end())
            count++;

        head2 = head2->next;
    }
    return count;
}
int main()
{
    struct Node* head1 = NULL;
    struct Node* head2 = NULL;

    implementLinkedList (&head1,11);
    implementLinkedList (&head1, 6);
    implementLinkedList (&head1, 1);
    implementLinkedList (&head1, 8);

    implementLinkedList (&head2, 5);
    implementLinkedList (&head2, 3);
    implementLinkedList (&head2, 1);
    implementLinkedList (&head2, 9);

    int sum = 9;

    cout << "Count = "<< getPairOfsum (head1, head2, sum);
    return 0;
}
Count = 2

کد جاوا برای شمارش جفت از دو لیست پیوند یافته که مجموع آنها برابر با یک مقدار مشخص است

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;

class PairOfSumInLinkedList1
{
    public static int getPairOfsum(LinkedList<Integer> head1, LinkedList<Integer> head2, int sum)
    {
        int count = 0;

        HashSet<Integer> SET = new HashSet<Integer>();

        Iterator<Integer> itr1 = head1.iterator();
        while (itr1.hasNext())
        {
            SET.add(itr1.next());

        }

        Iterator<Integer> itr2 = head2.iterator();
        while (itr2.hasNext())
        {
            if (!(SET.add(sum - itr2.next())))
                count++;

        }
        return count;
    }
    public static void main(String[] args)
    {
        Integer arr1[] = {11, 6, 1, 8};
        Integer arr2[] = {5, 3, 1, 9};

        LinkedList<Integer> head1 = new LinkedList<>(Arrays.asList(arr1));

        LinkedList<Integer> head2 = new LinkedList<>(Arrays.asList(arr2));

        int x = 9;

        System.out.println("Count = " + getPairOfsum(head1, head2, x));
    }
}
Count = 2

تحلیل پیچیدگی

پیچیدگی زمان

O (n1 + n2) جایی که "n1" و "n2" تعداد عناصر موجود در لیست پیوندی هستند. ما قادر به دستیابی به پیچیدگی زمانی خطی هستیم. زیرا ما هم لیست های پیوندی را مرور کردیم و هم از HashSet استفاده کردیم.

پیچیدگی فضا

از آنجا که ورودی را در دو لیست پیوند خورده ذخیره کردیم و از HashSet استفاده کردیم. ما یک راه حل خطی برای پیچیدگی فضای داریم.