lepeisi
BAN USERFirst of all, i didn't say it is the fastest.
Second, the big O notation is a set which consider asymptoticly performance.
Therefore O(n+nlogn) is exactly the same as O(nlogn).
Do not write things like this or O(4n). It is misleading and only showing people your lack of understanding of asymptotic notation.
Just do bfs from vertex with zero indegree.
Delete vertex of indegree 0 and all its outgoing edges from the graph.
Continue doing so until no more indegree 0 vertex.
If the graph still have vertexes, then it has cycle. Return what ever the reviewer want (could be null or the vertexes deleted)
If the graph do not have vertexes then the deleted vertexes is in topological order.
We could keep a stack for the deleted vertexes and return it as the answer.
But that is not O(log N) in worst or average case. It is O(log N) in the best case only, although I do agree DFS is better on average than BFS.
In worst case the tree is linear and your node can be the last.
In general, your tree can still be inbalanced and you may have to traversal n/2 or n/3 nodes to find the answer.
O(log(10,n)) ~ O(1) for 32 bit int. Note this is for 0 to n.
For m to n just call it twice and subtract
public int countDigitTwo(int n) {
if (n <= 0) return 0;
int q = n, x = 1, ans = 0;
do {
int digit = q % 10;
q /= 10;
ans += q * x;
if (digit == 2) ans += n % x + 1;
if (digit > 2) ans += x;
x *= 10;
} while (q > 0);
return ans;
}

lepeisi
November 28, 2015 Transform given set of IP addresses into 32 bit unsigned int
Apply quick sort or merge sort.
Transform it back to the ip addresses. O(n*logn).
Or you can write a comparator with transform the ip to int on the fly O(n*logn).
The former is faster. The latter save a bit on space.
public int maxCoins(int[] nums) {
int n = nums.length;
int[][] dp = new int[n][n];
for (int k = 2; k < n; ++k) {
for (int left = 0; left < n  k; ++left) {
int right = left + k;
for (int i = left + 1; i < right; ++i)
dp[left][right] = Math.max(dp[left][right], nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]);
}
}
return dp[0][n  1];
}

lepeisi
November 27, 2015 public int maxProfit(int[] prices) {
int sell = 0, prev_sell = 0;
int buy = Integer.MIN_VALUE, prev_buy;
for (int price : prices) {
prev_buy = buy;
buy = Math.max(prev_sell  price, prev_buy);
prev_sell = sell;
sell = Math.max(prev_buy + price, prev_sell);
}
return sell;
}

lepeisi
November 22, 2015 Open Chat in New Window
Just use the last bit to determine whether it is odd.
1 for true, 0 for false
or this
 lepeisi December 07, 2015