LinkedListComponents [source code]

public class LinkedListComponents {
static
/******************************************************************************/
class Solution {
    public int numComponents(ListNode head, int[] G) {
        int N = G.length;
        Map<Integer, Set<Integer>> adj_lists = new HashMap<> ();
        for (int node : G) {
            adj_lists.put (node, new HashSet<> ());
        }
        while (head != null) {
            if (head.next != null) {
                if (adj_lists.containsKey (head.val) && adj_lists.containsKey (head.next.val)) {
                    adj_lists.get (head.val).add (head.next.val);
                    adj_lists.get (head.next.val).add (head.val);
                }
            }
            head = head.next;
        }
        Set<Integer> visited = new HashSet<> ();
        int num_cc = 0;
        for (int node : adj_lists.keySet ()) {
            if (!visited.contains (node)) {
                dfs (node, visited, adj_lists);
                num_cc++;
            }
        }
        return num_cc;
    }

    void dfs (int root, Set<Integer> visited, Map<Integer, Set<Integer>> adj_lists) {
        visited.add (root);
        for (int neighbor : adj_lists.get (root)) {
            if (!visited.contains (neighbor))
                dfs (neighbor, visited, adj_lists);
        }
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        LinkedListComponents.Solution tester = new LinkedListComponents.Solution();
    }
}

读完题目感觉不难, 建一个graph然后走DFS找CC就行了;

也是很轻松解决了;

这题其实想复杂了, 真正的做法其实就是一个分段算法就行了; 这个是一个LinkedList, 单向的, 所以如果是CC, 就是连在一起, 很简单的, 所以只要走一遍, 看分段, 就完事了;

当然, 我这个笨办法就当做是练习基本功了, 不过这种做法面试的时候多半是要被喷的;

注意当我从这个LinkedList找graph的时候, 还是站在parent的地方来看link, 这个也是一个很基本的LinkedList操作习惯了;

editorial

Approach #1: Grouping [Accepted]

Intuition

Instead of thinking about connected components in G, think about them in the linked list. Connected components in G must occur consecutively in the linked list.

没错, 这题其实本身是不难, 怎么做都能做出来, 关键就是你能不能想到一个最优的解法; 这种题目也挺奇葩的. 如果你拿到题目立刻就跟我一样, 被CC的思路给带跑偏了, 那么这题直接最优解的机会就没有了;

Algorithm

Scanning through the list, if node.val is in G and node.next.val isn't (including if node.next is null), then this must be the end of a connected component.

For example, if the list is 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7, and G = [0, 2, 3, 5, 7], then when scanning through the list, we fulfill the above condition at 0, 3, 5, 7, for a total answer of 4.

class Solution {  
    public int numComponents(ListNode head, int[] G) {  
        Set<Integer> Gset = new HashSet();  
        for (int x: G) Gset.add(x);  

        ListNode cur = head;  
        int ans = 0;  

        while (cur != null) {  
            if (Gset.contains(cur.val) &&  
                    (cur.next == null || !Gset.contains(cur.next.val)))  
                ans++;  
            cur = cur.next;  
        }  

        return ans;  
    }  
}

他这个写法你仔细看, 是要处理收尾的; 不过他比较狡猾, 他用prelook的思路, 在一个逻辑位置直接把收尾一起处理了: 如果是下降沿, 或者后面没有了: 就开始trigger收分段的操作; 这个操作实际上我自己也用过, 就是最近ML的hw5写的那个小脚本的时候, 我就用的这个思路了;

复杂度是O(N + G.length). 分段算法嘛. 注意这个加法不能忽略, preprocess的时间也要算的;

UNFINISHED

uwi:

class Solution {  
    public int numComponents(ListNode head, int[] G) {  
        boolean[] hit = new boolean[10005];  
        for(int v : G)hit[v] = true;  

        int rep = 0;  
        int con = 0;  
        while(head != null){  
            if(hit[head.val]){  
                if(rep == 0)con++;  
                rep++;  
            }else{  
                rep = 0;  
            }  

            head = head.next;  
        }  
        return con;  
    }  
}

看来是有点门道的, 我这个肯定是做复杂了;

这个就是分段算法, 不过这里是偷师成功, 看到了uwi的分段算法的思路; 另外他这个hit数组其实就是冒充set来用, 这个就是他比赛的时候抢分的小技巧, 不用管; 面试的时候别搞这种事情;

主要是看他的这个分段算法;

两个变量含义不难理解, rep就是当前如果在一个run里面, 这个run的长度, 然后con就是包括当前run, 已经得到的run的个数;

然后逻辑就比较简单; 他更新con的时间点, 是根据进入run的上升沿来判断: 如果我们看到一个hit, 然后下面rep是肯定要++的, 但是我们判断一下这个++是不是0->1的上升沿, 如果是的话, 说明con也要++了; 然后如果没有hit, 把rep给清空就行了, 这个在比如1 1 1 0 0 0 1 1 1 这样的, 中间段的三个0每一次都要做一个, 不过最后也是不复杂; 这样一个分段算法真的是相当的简练; 核心就是要理解, rep这个东西看起来好像对分段算法本身没有意义, 但是用他来维护con, 要比自己直接在收尾的时候去维护, 用trigger思维来做要方便的多;

cchao:

class Solution {  
public:  
    int numComponents(ListNode* head, vector<int>& G) {  
        set<int> s;  
        for (int x : G) s.insert(x);  
        bool vis = false;  
        int ans = 0;  
        for (ListNode *x = head; x != nullptr; x = x->next) {  
            bool t = s.count(x->val) != 0;  
            if (!vis && t) {  
                ans++;  
            }  
            vis = t;  
        }  
        return ans;  
    }  
};

这个是跟uwi类似的算法, 不过他把rep换成了一个boolean; 高手之间还是有点相通的地方的;

Problem Description

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.

Difficulty:Medium
Total Accepted:1.3K
Total Submissions:3K
Contributor:awice
Companies
google
Related Topics
linked list