1.问题
给定链表头结点 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。
2.说明
如果 N 是给定链表 head 的长度,1 <= N <= 10000。
链表中每个结点的值所在范围为 [0, N - 1]。
1 <= G.length <= 10000
G 是链表中所有结点的值的一个子集.
输入说明:
首先输入链表长度len,然后输入len个整数,以空格分隔。
再输入G的大小m,然后输入m个整数,以空格分隔。
输出说明:
输出一个整数,表示结果。
3.范例
输入范例:
4
0 1 2 3
3
0 1 3
输出范例:
2
4.思路
遍历链表,对于head中的每个节点 a 判断其 a->val 是否在G中存在,如果存在那么G中对应的a->val 很可能是一个组件;此时还得检查一下 a->next(假设为 b = a->next), 如果 b->val 也在G中,那么 (a->b)形成了一个更大的子链表,以b结尾的链表很可能是一个组件;
算法思路:如果当前的节点在G 中,且下一个节点不在G 中,就找到了一个组件的尾节点,可以将答案加 1;
首先创建一个SET,把G中元素复制到SET中,然后从头开始遍历链表,如果当前结点在SET中且下一个结点不在SET中就res++,返回结果
5.代码
#include<iostream> #include<math.h> #include<vector> #include<stdio.h> #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 numComponents2(ListNode* head, vector<int>& G) { //首先创建一个SET,把G中元素复制到SET中, //然后从头开始遍历链表,如果当前结点在SET中且下一个结点不在SET中就res++, //返回结果 set<int> s; for(int i=0;i<G.size();i++) { s.insert(G[i]); } ListNode *p=head; if(p==NULL) return 0; int res=0; while(p) { if(s.find(p->val)!=s.end()) { if(p->next==NULL||s.find(p->next->val)==s.end()) res++; } p=p->next; } return res; } }; 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() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); 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().numComponents2(head,G); cout<<res<<endl; return 0; }
标签:力扣,head,ListNode,int,结点,next,链表,组件 From: https://www.cnblogs.com/ohye/p/17725776.html