ধরুন আমরা একটি মাথা দিয়েছি; এটি অনন্য পূর্ণসংখ্যা মান ধারণকারী একটি লিঙ্ক তালিকার প্রধান নোড। এখন আমাদের তালিকা G দেওয়া হয়েছে, লিঙ্ক করা তালিকার মানগুলির একটি উপসেট। আমাদের G-তে সংযুক্ত উপাদানের সংখ্যা খুঁজে বের করতে হবে, যেখানে দুটি মান সংযুক্ত করা হয় যদি তারা সংযুক্ত তালিকায় পরপর উপস্থিত হয়। সুতরাং যদি তালিকাটি [0,1,2,3] এবং G =[0,1,3] এর মত হয়, তাহলে আউটপুট 2 হবে, যেহেতু 0 এবং 1 সংযুক্ত রয়েছে, তাই দুটি তালিকা রয়েছে [0,1] এবং [৩]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- ret :=0, একটি সেট s তৈরি করুন এবং s-এ G-এর সমস্ত উপাদান সন্নিবেশ করুন
- পতাকা :=মিথ্যা
- যদিও হেড শূন্য নয়
- x :=মাথার মান
- যদি s এর x থাকে, তাহলে
- পতাকা মিথ্যা হলে, ret 1 দ্বারা বাড়ান
- পতাকা :=সত্য
- অন্যথায় পতাকা সেট করুন :=মিথ্যা
- মাথা :=মাথার পাশে
- রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
class Solution {
public:
int numComponents(ListNode* head, vector<int>& G) {
int ret = 0;
set < int > s;
for(int i = 0; i < G.size(); i++)s.insert(G[i]);
bool flag = false;
while(head){
int x = head->val;
if(s.count(x)){
if(!flag) ret++;
flag = true;
}else flag = false;
head = head->next;
}
return ret;
}
};
main(){
vector<int> v1 = {0,1,2,3};
vector<int> v2 = {0,1,3};
ListNode *h1 = make_list(v1);
Solution ob;
cout << (ob.numComponents(h1, v2));
} ইনপুট
[0,1,2,3] [0,1,3]
আউটপুট
2
