zouzhile
BAN USERpublic Node reverse(Node head, int k) {
// after reverse, the return node is
// the last node in the first K nodes in the original list
// which is also the head node in the reversed list
Node returnNode = null;
// for the ith K sub list, the two "previous" pointers
// would point to the (i-1)th K sub list's head and tail "after" reverse
// This means, after reversing 3,2,1, previousTail points to 3 and previousHead points 1
Node previousTail = null;
Node previousHead = null;
while(head != null) { // not reached the end of the list
Node tail = head;
for(int i = 1; i < k & tail.next() != null; i ++) {
tail = tail.next();
}
Node nextHead = tail.next();
reverse(head, tail);
if( previousHead == null || previousTail == null) {
// first K sub list
previousHead = tail;
previousTail = head;
returnNode = tail;
} else
previousTail.setNext(tail);
head.setNext(nextHead);
head = nextHead;
}
return returnNode;
}
private Node reverse(Node current, Node tail) {
if(current == tail) {
return current;
}
Node next = reverse(current.next(), tail);
next.setNext(current);
return current;
}
// for pair i, the child is children[i], parent is parents[i]
public BinaryTreeNode convert(int[] children, int[] parents) {
HashMap<Integer, BinaryTreeNode> nodes = new HashMap<>();
// resolve root
int rootValue = this.getRootValue(children, parents);
BinaryTreeNode root = new BinaryTreeNode(rootValue);
nodes.put(rootValue, root);
for(int i = 0; i < children.length; i ++) {
int child = children[i];
BinaryTreeNode childNode = nodes.get(child);
if(childNode == null) {
childNode = new BinaryTreeNode(child);
nodes.put(child, childNode);
}
int parent = parents[i];
BinaryTreeNode parentNode = nodes.get(parent);
if(parentNode == null) {
parentNode = new BinaryTreeNode(parent);
nodes.put(parent, parentNode);
}
// set parent child relationship
childNode.setParent(parentNode);
if(parentNode.getLeftChild() == null)
parentNode.setLeftChild(childNode);
else
parentNode.setRightChild(childNode);
}
return root;
}
private int getRootValue(int[] children, int[] parents) {
HashSet<Integer> ancestors = new HashSet<>();
for(int parent : parents)
ancestors.add(parent);
for(int child : children)
ancestors.remove(child);
return ancestors.iterator().next();
}
public class C1_33RealTimeCounter {
static class Timer {
/*
timer in nanoseconds accurracy
*/
public static long time() {
return new Date().getTime() * 1000;
}
/**
*
* @param start the start time in nanoseconds
* @param end the end time in nanoseconds
* @return
*/
public static int diff(long start, long end) {
return (int) (end - start) / 1000000;
}
}
class CyclicBuffer {
int[] data = new int[86400];
int beginOffset = 0;
int endOffset = 0;
/**
*
* @param value current counter value
* @param seconds how many seconds passed since last append
*/
public void append(int value, int seconds) {
for(int i = 1; i <= seconds; i ++) {
endOffset = (endOffset + i) % data.length;
data[endOffset] = value;
}
beginOffset = (beginOffset + seconds) % data.length;
}
public int get(int distanceFromEnd) {
int offset = (endOffset + data.length - distanceFromEnd) % data.length;
return (int)data[offset];
}
}
private int counter = 0;
private long lastIncrementTime = -1;
private CyclicBuffer buffer = new CyclicBuffer();
public void increment() {
long currentTime = Timer.time();
if(lastIncrementTime < 0)
lastIncrementTime = currentTime;
int secondsSinceLastIncrement = Timer.diff(lastIncrementTime, currentTime);
counter ++;
buffer.append(counter, secondsSinceLastIncrement);
}
public int getCountInLastSecond() {
return buffer.get(0) - buffer.get(1);
}
public int getCountInLastMinute() {
return buffer.get(0) - buffer.get(60);
}
public int getCountInLastHour() {
return buffer.get(0) - buffer.get(3600);
}
public int getCountInLastDay() {
return buffer.get(0) - buffer.get(86399);
}
my earlier comment about MST is not right.
The following code is tested to work well.
public void printGraphCycles(Graph graph) {
HashSet<Vertex> visited = new HashSet<>();
HashSet<Vertex> candidates = new HashSet<>();
for(Vertex vertex : graph.vertexs()){
if(! visited.contains(vertex) && !candidates.contains(vertex))
DFS(graph, vertex, visited, candidates);
}
}
public void DFS(Graph graph, Vertex vertex, HashSet<Vertex> visited, HashSet<Vertex> candidates) {
/*
1 ---] 2
] /] \
| / | ]
| / | 3
| / | /
| [ | [
5 ----] 4
*/
candidates.add(vertex);
for(Vertex adj : graph.adj(vertex)) {
if(candidates.contains(adj)) {
// visited nodes may need to revisit to build the cycle
// so don't put visited.contains(adj) on the if condition.
// an example is node 4
// found cycle
printCycle(vertex, adj);
} else {
adj.setParent(vertex); // build the trace back
DFS(graph, adj, visited, candidates);
}
}
candidates.remove(vertex);
visited.add(vertex);
}
You can generate the minimum spanning tree (MST) of the graph, which is rather simple with BFS. Any graph edges not in the MST is possible to introduce a cycle.
For each edge not in MST, let source_vertex be the source of the edge, and end_vertex be the end of the edge. If end_vertex is ancestor of source_vertex, then there is a loop between source_vertex and end_vertex. The loop can be identified by calling getParent() from source_vertex, until meet the end_vertex.
The problem itself is tricky, it says constant space but doesn't require it to be storage efficient.
The solution is:
int maxValue = tree.getMaxValue() // by keeping visiting right most branch
int[] array = new int[maxValue] // not storage efficient
for each node value in the tree, set array[value] = 1 // O(n)
for each node value in the tree, check whether array[K-value] exists. If exists, print the pair. // O(n)
Thus the solution is O(n) and the storage is a constant value depending the largest node value.
Maintain a binary search tree of k nodes. Scan the input list, if current node value is larger than the smallest value of the tree nodes, remove that node and insert current node value into the binary search tree.
- zouzhile February 27, 2014Time complexity is O(nlogk).