本文共 2203 字，大约阅读时间需要 7 分钟。

题目：

We are given head, the head node of a linked list containing unique integer values.

We are also given the list G, a subset of the values in the linked list.

Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

Example 1:

Input: head: 0->1->2->3 G = [0, 1, 3] Output: 2 Explanation:  0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Example 2:

Input:  head: 0->1->2->3->4 G = [0, 3, 1, 4] Output: 2 Explanation:  0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are、】the two connected components.

Note:

If N is the length of the linked list given by head, 1 <= N <= 10000.

The value of each node in the linked list will be in the range [0, N - 1].

1 <= G.length <= 10000.

G is a subset of all values in the linked list.

解释：

看下题目中所给的第二个例子: liked list: 0->1->2->3->4 I highlighed the subset G in linked list with* italic * 用斜体来强调了G中的子集，题目转换为有多少个斜体部分，一个斜体部分就是一个connected components，我们只需要数斜体部分的尾部的个数即可。 python代码：

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    def numComponents(self, head, G):        """        :type head: ListNode        :type G: List[int]        :rtype: int        """        res=0        setG=set(G)        while head!=None:            if (head.val in setG ) and (head.next==None or head.next.val not in setG):                res+=1            head=head.next        return res

为什么同样的代码，c++超时？

c++用set速度查找太慢了，需要用一个长度为10000的bool类型的数组来判断当前的数字是否在G中出现。 c++代码：

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */#include 
   
    using namespace std;class Solution {
   public:    int numComponents(ListNode* head, vector
    
     & G) {
           vector
     
       setG(10000,false);        for(auto num:G)            setG[num]=true;        int result=0;        while(head)        {
               if (setG[head->val]&& (!head->next || !setG[head->next->val] ))                result++;            head=head->next;        }        return result;    }};
     
    
   

总结：

转载地址：http://vwmcn.baihongyu.com/