C++ 中的链表组件

假设给我们一个头部；这是包含唯一整数值的链表的头节点。现在还给了我们列表 G，是链表中值的子集。我们必须找到 G 中的连通组件数，如果两个值在链表中连续出现，则它们是连通的。因此，如果列表为 [0,1,2,3] 并且 G = [0,1,3]，则输出将为 2，因为 0 和 1 是连通的，所以有两个列表 [0,1] 和 [3]。

要解决此问题，我们将遵循以下步骤 -

  • ret := 0，创建一个集合 s，并将 G 中的所有元素插入 s
  • flag := false
  • 当 head 不为 null 时
    • x := head 值
    • 如果 s 有 x，则
      • 如果 flag 为 false，则 ret 增加 1
      • flag := true
    • 否则，将 flag 设为 false
    • head := head 的下一个
  • 返回 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

更新于: 04-May-2020

343 次浏览

开启您的 职业 生涯

完成课程后，获得认证

开始
广告