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 in-degree.
Delete vertex of in-degree 0 and all its outgoing edges from the graph.
Continue doing so until no more in-degree 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;
}
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];
}
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;
}
Just use the last bit to determine whether it is odd.
1 for true, 0 for false
or this
- lepeisi December 07, 2015