有一些想法是利用了图的思想

128. Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given[100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is[1, 2, 3, 4]. Return its length:4.

Analysis

对于每个数k我们可以从集合里搜索k+1,k+2,k-1,k-2的存在可能性 如果一直是连续存在的我们更新当前长度len++ 如果不是 停止循环

每用一次数字 将该数字从集合中去除 因为每个数字不可能出现在两个不同的连续数列之中 整个过程可以类比TP Sort只不过用了HashSet

399. Evaluate Division

代码

建立图一个是用List还有一个是用HashSet 这里给了两个点 如果用HashSet可以很快判断所给的点在图里是不是存在。

然后就是对所给的数对进行DFS DFS的过程中计算值 如果到达终点则返回结果

Runtime of DFS: O(V+E) vertexs and edges.

常规

133. Clone Graph

Basic Graph Question that test DFS/BFS Use a hashMap that acts like a visited array

Create a cloned-graph not a reference. Start from the given root node, check whether it has been created and move to the the neighbors. If it is not created yet, create a new one and add the mapping

I 递归DFS (It seems that the neighbors array exist from the start)

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null)return null;
        UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
        HashMap<UndirectedGraphNode,UndirectedGraphNode> map = new HashMap<UndirectedGraphNode,UndirectedGraphNode>();
        map.put(node,copy);
        helper(node,map);
        return copy;
    }
    //The map stores the mapping from the orginal nodes to the copy nodes, we assumed that the passed-in node have
    //been visited or built
    public void helper(UndirectedGraphNode pre,HashMap<UndirectedGraphNode,UndirectedGraphNode> map){
        if(pre == null)return;
        //check the neighbors if it is not in the keyset then create a corresponding copy node for it 
        for(UndirectedGraphNode node: pre.neighbors){
            if(!map.containsKey(node)){
                UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
                map.put(node,newNode);
                helper(node,map);
            }
            map.get(pre).neighbors.add(map.get(node));
        }
    }
}

II 非递归DFS

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null)return null;
        UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
        HashMap<UndirectedGraphNode,UndirectedGraphNode> map = new HashMap<UndirectedGraphNode,UndirectedGraphNode>();
        map.put(node,copy);
        Stack<UndirectedGraphNode> stack = new Stack();
        stack.push(node);
        while(!stack.isEmpty()){
            UndirectedGraphNode cur = stack.pop();
            for(UndirectedGraphNode i: cur.neighbors){
                if(!map.containsKey(i)){
                    UndirectedGraphNode newNode = new UndirectedGraphNode(i.label);
                    map.put(i,newNode);
                    stack.push(i);
                }
                map.get(cur).neighbors.add(map.get(i));
            }
        }
        return copy;
    }
}