Daily Archives: July 22, 2016

Clone Graph

leetcode 133.

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization:Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

  1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  2. Second node is labeled as 1. Connect node 1 to node 2.
  3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Solution. Learned from here. Below is the DFS solution. I like this solution because it is a universal method. It can solve problem like Copy List with Random Pointer(github). Below is the code

public static UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    return clone(node, new HashMap<>());
}

private static UndirectedGraphNode clone(UndirectedGraphNode node, HashMap<Integer, UndirectedGraphNode> hm) {
    if (node == null) {
        return null;
    }
    if (hm.containsKey(node.label)) {
        return hm.get(node.label);
    }
    UndirectedGraphNode cloneNode = new UndirectedGraphNode(node.label);
    hm.put(cloneNode.label, cloneNode);
    for (UndirectedGraphNode neighbor : node.neighbors) {
        cloneNode.neighbors.add(clone(neighbor, hm));
    }
    return cloneNode;
}

Check my code on github.

Gas station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Solution.

We set diff[i] = gas[i] – cost[i]. First of all, there is always a result if total sum of diff is greater than 0, or there won’t be a result.

Consider below cases:

gas[]  = [3,  2,  0, 0,   1,  2,  2]
cost[] = [2,  1,  1,  1,   2,  3,  0]
diff[] =  [1,  1, -1, -1, -1, -1,  2]

Let’s consider about diff[]. Basically, we need to find a point i in diff. And starting from this point i, move after it and count sum[diff[i], … ]. In this process, any j which is “behind” i should have sum[diff[i], …, diff[j]] >= 0. 

We have this assumption for point i: if j is the first element “behind” i which makes sum[diff[i], …, diff[j]] < 0, then any element between (i, j) has sum[diff[i], …, diff[k]] < 0.

Let’s do a rough assumption by using a line. j is the first element after i, which makes sum[i….j] < 0. So we have sum[i…j] < 0, sum[i…k] >= 0

Besides we know sum[i…j] = sum[i…k] + sum[k…j]. So we can conclude that sum[k…j] < 0.

gasstation

Once we know this, we just do the sum of diff. Whenever the sum is less than zero, we set target to next element. Until we find an element which makes the sum is greater than 0 toward the end.

public int canCompleteCircuit(int[] gas, int[] cost) {
    // test see if there is a result.
    int total = 0;
    for (int i = 0; i < gas.length; i++) {
        total += gas[i] - cost[i];
    }
    if (total < 0) {
        return -1;
    }
    // calculate the aggregation until we find a position which the aggregation from it to the end is greater than or equal to 0
    int aggr = 0, ans = 0;
    for (int i = 0; i < gas.length; i++) {
        aggr += gas[i] - cost[i];
        if (aggr < 0) {
            ans = i + 1;
            aggr = 0;
        }
    }
    return ans;
}

Check my code on github.