作者:
晚于: 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个整数，以空格分隔。
输出说明 :
输出一个整数，表示结果。
输入范例 :
4 0 1 2 3 3 0 1 3
输出范例：
2
#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; }
原文：https://www.cnblogs.com/zmmm/p/13616452.html