4 链表组件（817）

作者: Turbo时间限制: 1S章节: DS:数组和链表

晚于: 2020-07-08 12:00:00后提交分数乘系数50%

截止日期: 2020-07-15 12:00:00

问题描述 :

给定链表头结点 head，该链表上的每个结点都有一个唯一的整型值。

同时给定列表 G，该列表是上述链表中整型值的一个子集。

返回列表 G 中组件的个数，这里对组件的定义为：链表中一段极长连续结点的值（该值必须在列表 G 中）构成的集合。极长的含义是：这段连续结点的前面或后面结点不属于G。

示例 1：

输入:

head: 0->1->2->3

G = [0, 1, 3]

输出: 2

解释:

链表中,0 和 1 是相连接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一个组件，同理 [3] 也是一个组件，故返回 2。

示例 2：

输入:

head: 0->1->2->3->4

G = [0, 3, 1, 4]

输出: 2

解释:

链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。

说明：

如果 N 是给定链表 head 的长度，1 <= N <= 10000。

链表中每个结点的值所在范围为 [0, N - 1]。

1 <= G.length <= 10000

G 是链表中所有结点的值的一个子集.

可使用以下代码，完成其中的numComponents函数，其中形参head指向无头结点单链表，G为列表，返回组件的个数。

#include<iostream>

#include<vector>

using namespace std;

struct ListNode

{

int val;

ListNode *next;

ListNode() : val(0), next(NULL) {}

ListNode(int x) : val(x), next(NULL) {}

ListNode(int x, ListNode *next) : val(x), next(next) {}

};

class Solution {

public:

int numComponents(ListNode* head, vector<int>& G) {

//填充本函数完成功能

}

};

ListNode *createByTail()

{

ListNode *head;

ListNode *p1,*p2;

int n=0,num;

int len;

cin>>len;

head=NULL;

while(n<len && cin>>num)

{

p1=new ListNode(num);

n=n+1;

if(n==1)

head=p1;

else

p2->next=p1;

p2=p1;

}

return head;

}

int main()

{

vector<int> G;

int m,data,res;

ListNode* head = createByTail();

cin>>m;

for(int i=0; i<m; i++)

{

cin>>data;

G.push_back(data);

}

res=Solution().numComponents(head,G);

cout<<res<<endl;

return 0;

}

输入说明 :

首先输入链表长度len，然后输入len个整数，以空格分隔。

再输入G的大小m，然后输入m个整数，以空格分隔。

输出说明 :

输出一个整数，表示结果。

输入范例 :

输出范例：

#include<iostream>
#include<vector>
#include <set>
using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(NULL) {}
    ListNode(int x) : val(x), next(NULL) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int numComponents(ListNode* head, vector<int>& G) {
      
        set<int> st;
        for( int i = 0; i < G.size(); ++i )
            st.insert(G[i]);
   
        int sum = 0;
        while( head != NULL )
        {
            if(st.find(head->val) != st.end() )
            {
                sum++;
                while( st.find(head->val) != st.end() )
                {
                    head = head->next;
                    if(!head)
                    {
                        break;
                    }
                }
            }
            else
                head = head->next;
        }
        return sum;

    }
};


ListNode *createByTail()
{
    ListNode *head;
    ListNode *p1,*p2;
    int n=0,num;
    int len;
    cin>>len;
    head=NULL;
    while(n<len && cin>>num)
    {
        p1=new ListNode(num);
        n=n+1;
        if(n==1)
            head=p1;
        else
            p2->next=p1;
        p2=p1;
    }
    return head;
}
int main()
{
    vector<int> G;
    int m,data,res;
    ListNode* head = createByTail();
    cin>>m;
    for(int i=0; i<m; i++)
    {
        cin>>data;
        G.push_back(data);
    }
    res=Solution().numComponents(head,G);
    cout<<res<<endl;
    return 0;
}