C++のリンクリストコンポーネント

頭を与えたとしましょう。これは、一意の整数値を含むリンクリストのヘッドノードです。これで、リンクリストの値のサブセットであるリストGも与えられます。 Gで連結成分の数を見つける必要があります。ここで、2つの値がリンクリストに連続して表示される場合、それらは連結されています。したがって、リストが[0,1,2,3]のようで、G =[0,1,3]の場合、0と1が接続されているため、出力は2になります。したがって、2つのリスト[0,1]と[3]。

これを解決するには、次の手順に従います-

• ret：=0、集合sを作成し、Gのすべての要素をsに挿入します
• フラグ：=false
• ヘッドがnullではない場合
  • x：=頭の値
  • sにxがある場合、
    • フラグがfalseの場合、retを1増やします
    • フラグ：=true
  • それ以外の場合はフラグを設定します：=false
  • 頭：=頭の次
• return ret

理解を深めるために、次の実装を見てみましょう-

例

#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