大家一起學AI

該題Linked List Components的題目如下所示，要計算出共有幾段鏈結串列，範例1的鏈結串列有四個節點，分別為1至4，若有一個陣列G的元素為0、1、3，等於將鏈結串列從元素2的地方切開，切開後鏈結串列為2段，所以輸出為2，而範例2可以看到陣列G一樣少了元素2，因此，輸出結果也為2。

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.

作法解析:將G陣列放置於hash table中，即能於鏈結串列中的每個元素進行數值檢查，若一個數值不存在，則可知道鏈結串列會被多分成一段。

程式碼:

/**
 * 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) {
        int counter = 0;
        unordered_map<int, bool> m;
        bool flag = false;
        
        for (int i = 0; i < G.size(); i++)
            m[G[i]] = 0;
             
        while(head != NULL)
        {
            if (m.count(head->val))
            {
                if (flag == false)
                {
                    counter++;
                    flag = true;
                }
            }
            else    
                flag = false;       
            head = head->next;
        }
        return counter;
    }
};

1.宣告一個hash table變數，並將G陣列之值放入。

2.宣告一個旗標為fasle，若元素存在(m.count(head->val))，且旗標為false (if (flag == false))，則進行計數。