817链表组件

817链表组件

下面是题目

 /*
 a linked list containing unique integer values
给定一个链表（链表结点包含一个整型值）的头结点 head。
同时给定列表 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 是链表中所有结点的值的一个子集.
 */

下面是题目给我们的代码模板

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int numComponents(ListNode* head, vector<int>& G) {

    }
};

思路很简单很简单，就是看看链表中的val在不在vector内，在的话，一直找的不是为止，然后更新组件个数，不在的话节点后移，完成迭代

但是我自己死活搞不出来！！！！！！！

//以下是我用find函数直接在vector数组中找啊找的代码，基本思路和用set一样，测试点也都过了，但是很可惜超出了时间限制~~~
class Solution {
public:
    int numComponents(ListNode* head, vector<int>& G) {
        int num = 0;
        ListNode*cur = head;
        while(cur)
        {
            if(find(G.begin(),G.end(),cur->val)!=G.end())
            {
                num++;
                while(find(G.begin(),G.end(),cur->val)!=G.end())
                {
                    cur = cur->next;
                    if(!cur)break;
                }             
            } else  cur  = cur->next;
        }
        return num;
    }
};

 //看了别人的思路后，发现还是要用set或者bool数组才能解决
class Solution {
public:
    int numComponents(ListNode* head, vector<int>& G) {
        //首先把数组全部存入---等于去重+排列
    	set<int> m_set;
        for( int i = 0; i < G.size(); ++i ){
        	m_set.insert(G[i]);
        }

        int Comnum = 0;
        while( head != NULL ){
            //一旦找到了，要把左右连续的都遍历光，val不出现在set
        	if( m_set.find(head->val) != m_set.end() ){
        		Comnum++;
        		while( m_set.find(head->val) != m_set.end() ){
        			head = head->next;
        			if(!head) break;
        		}
        	}
            else head = head->next;
        }
        return Comnum;
    }
};

还有一种方法，我认为更加巧妙，就是利用bool数组来判断是否存储，空间上应该占用的内存更小

class Solution {
public:
    int numComponents(ListNode* head, vector<int>& G) {
       if (!head)
             return 0;
        //首先按照最大的数据建立一个bool数组
        //然后把所有在vector中出现的值全部标成1来达到set的作用
         bool m[10000] = {0};
         for (int i = 0; i < G.size(); i++) {
             m[G[i]] = 1;
         }
         ListNode* p = head;
         int count = 0;
         bool b = 0;
        //开始遍历，当b=0且val值在数组中的映射为1的时候，count++。
        //然后将b设置成m[p->val]，p = p->next
        //这样，如果链表中连续的数字出现，那么b=1，就不会进入到判断当中去
        //一直到下一个组件开始的时候 b=0，才会开始下一次判断
        //我认为原理还是一样的，但是这种设置就非常的妙。达到了四两拨千斤的效果
         while (p) {
             if (!b && m[p->val]) {
                 count++;
             }
             b = m[p->val];
             p = p->next;
         }
         return count;
    }
};