ftalm

Sunday, December 20, 2015

TO-DO 12/20/2015

REVIEW:
Dijstra and Bellman-ford algorithm, RIP algorithm
Floyd最短路算法还有max flow这些基础图论的东西

fibonacci number matrix calculation

http://www.gocalf.com/blog/calc-fibonacci.html

Saturday, December 19, 2015

[leetcode] Clone Graph

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) return null;
        HashMap<UndirectedGraphNode, UndirectedGraphNode> cloneNodes = 
                    new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
        mapClone(node, cloneNodes);
        UndirectedGraphNode[] allNodes = cloneNodes.keySet()
                                            .toArray(new UndirectedGraphNode[cloneNodes.size()]);
        for (int i = 0; i < allNodes.length; i++){
            UndirectedGraphNode copyNode = cloneNodes.get(allNodes[i]);
            List<UndirectedGraphNode> neighbors = allNodes[i].neighbors;
            for (int j = 0; j < neighbors.size(); j++){
                copyNode.neighbors.add(cloneNodes.get(neighbors.get(j)));
            }
        }
        
        return cloneNodes.get(node);
    }
    
    
    public void mapClone(UndirectedGraphNode node, 
                HashMap<UndirectedGraphNode, UndirectedGraphNode> cloneNodes){
        if (cloneNodes.containsKey(node)) return;
        cloneNodes.put(node, new UndirectedGraphNode(node.label));
        List<UndirectedGraphNode> neighbors = node.neighbors;
        for (int i = 0; i < neighbors.size(); i++){
            mapClone(neighbors.get(i), cloneNodes);
        }
    }
}

[leetcode]Course Schedule

就是建立有向图查有没有cycle

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        HashMap<Integer, Node> lookup = new HashMap<Integer, Node>();
        for (int i = 0; i < prerequisites.length; i++){
            Node temp = lookup.containsKey(prerequisites[i][0])?
                        lookup.get(prerequisites[i][0]):new Node(prerequisites[i][0]);
            Node next = lookup.containsKey(prerequisites[i][1])?
                        lookup.get(prerequisites[i][1]):new Node(prerequisites[i][1]);
            temp.addNext(next);
            lookup.put(prerequisites[i][0], temp);
            lookup.put(prerequisites[i][1], next);
        }
        
        Integer[]nodes = (Integer[])lookup.keySet().toArray(new Integer[lookup.size()]);
        for (int i = 0; i < nodes.length; i++){
            if (!lookup.get(nodes[i]).checked && hasCycle(lookup, new HashSet<Integer>(), nodes[i].intValue())){
                return false;
            }
        }
        return true;
    }
    
    public boolean hasCycle(HashMap<Integer, Node> lookup, HashSet<Integer> visited, int current){
        Node curNode = lookup.get(current);
        curNode.checked = true;
        visited.add(current);
        List<Node> neighbors = curNode.nexts;
        for (int i = 0; i < neighbors.size(); i++){
            if (visited.contains(neighbors.get(i).classNum) || hasCycle(lookup, visited, neighbors.get(i).classNum)){
                return true;
            }
        }
        visited.remove(current);
        return false;
    }
}

class Node{
    int classNum;
    boolean checked;
    List<Node> nexts = new ArrayList<Node>();
    Node(int classNum){this.classNum = classNum;}
    void addNext(Node next){nexts.add(next);}
}

[leetcode]Graph Valid Tree

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (n == 1) return true;
        HashMap<Integer, List<Integer>> lookup = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < edges.length; i++){
            List<Integer> neighbors = lookup.containsKey(edges[i][0])?
                                      lookup.get(edges[i][0]):new ArrayList<Integer>();
            neighbors.add(edges[i][1]);
            List<Integer> neighbors2 = lookup.containsKey(edges[i][1])?
                                      lookup.get(edges[i][1]):new ArrayList<Integer>();
            neighbors2.add(edges[i][0]);
            lookup.put(edges[i][0], neighbors);
            lookup.put(edges[i][1], neighbors2);
        }
        if (lookup.size() != n) return false;
        boolean visited[] = new boolean[n];
        if (hasCycle(lookup, visited, -1, 0)) return false;
        for (int i = 0; i < visited.length; i++){
            if (!visited[i]) return false;
        }
        return true;
    }
    
    public boolean hasCycle(HashMap<Integer, List<Integer>> neighbors, boolean[] visited, int parent, int current){
        if (visited[current]) return true;
        visited[current] = true;
        List<Integer> neighbor = neighbors.get(current);
        for (int i = 0; i < neighbor.size(); i++){
            if (neighbor.get(i) != parent && hasCycle(neighbors, visited, current, neighbor.get(i))){
                return true;
            }
        }
        return false;
    }
}

Sunday, December 13, 2015

[leetcode]Remove Invalid Parentheses

public class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> result = new ArrayList<String>();
        HashSet<String> lookup = new HashSet<String>();
        Queue<String> queue = new LinkedList<String>();
        queue.add(s);
        queue.add(null);
        while (!queue.isEmpty()){
            String current = queue.poll();
            if (current == null){
                if (result.size() != 0) break;
                queue.add(null);
            }
            if (current != null && !lookup.contains(current)){
                lookup.add(current);
                if (isValid(current)) result.add(current);
                else{
                    for (int i = 0; i < current.length(); i++){
                        char temp = current.charAt(i);
                        if (temp == '(' || temp == ')'){
                            queue.add(current.substring(0,i)+current.substring(i+1));
                        }
                    }
                }
            }
        }
        return result;
    }
    
    
    private boolean isValid(String s){
        int count = 0;
        for (int i = 0; i < s.length(); i++){
            char current = s.charAt(i);
            if (current == '(') count++;
            else if (current == ')') count--;
            if (count < 0) return false;
        }
        
        return count == 0;
    }
}

Sunday, December 6, 2015

QuickSelection

http://marswork.logdown.com/posts/285570-algorithm-quick-select