C++의 연결 목록 구성 요소

<시간/>

우리가 머리를 주었다고 가정합니다. 이것은 고유한 정수 값을 포함하는 연결 목록의 헤드 노드입니다. 이제 연결 목록에 있는 값의 하위 집합인 목록 G도 제공됩니다. 연결 리스트에 연속적으로 나타나면 두 값이 연결되는 G에서 연결된 구성 요소의 수를 찾아야 합니다. 따라서 목록이 [0,1,2,3]이고 G =[0,1,3]인 경우 0과 1이 연결되어 있으므로 출력은 2가 되므로 두 개의 목록 [0,1]과 [3].

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ret :=0, 집합 s를 만들고 G의 모든 요소를 s에 삽입
플래그 :=거짓
head가 null이 아닌 동안
- x :=헤드 값
- s에 x가 있으면
  - 플래그가 거짓이면 ret를 1 증가
  - 플래그 :=참
- 그렇지 않으면 플래그 설정 :=false
- head :=머리 옆
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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]