runwithfullspeed
BAN USERlet NL[i,j] be the number of lands in the matrix A[i,j], then:
NL[i, j] = NL[i-1, j] + NL[i, j-1] - NL[i-1, j-1], if NL[i, j] is water.
NL[i, j] = NL[i-1, j] + NL[i, j-1] - NL[i-1, j-1], if NL[i, j] is land either NL[i-1,j] or NL[i, j-1] is land.
NL[i,j] = NL[i-1, j] + NL[i, j-1] - NL[i-1, j-1] - 1, if NL[i,j], NL[i-1,j] and NL[i,j-1] are land.
NL[i,j] = NL[i-1, j] + NL[i, j-1] - NL[i-1, j-1] +1, if NL[i,j] is land and NL[i-1,j] and NL[i, j-1] are not land.
The time complexity is the size of the matrix.
for a none leaf node of BST, elements in its left sub tree are smaller than it, and elements in its right sub tree are bigger than it. So, min difference can only happen between a none leaf node and its direct children nodes. So, the min difference of a BST is the min difference of each none leaf node and their direct children node. We can use dynamic programming to compute difference between a none leaf node and its children nodes, and propagate the difference up to it parent.
let MD(n) is the min difference than can be gotten from the sub tree that are rooted at node n. Then:
MD(n) = min(value(n)-value(child of n), MD(child of n))
The time complexity is in linear to the size of the tree.
Use dynamic programming, find max sum for each node and remember the value.
let MS(n) be the max sum for node n, then:
MS(n) = max(MS(child of n)) + value(n),
if n is leaf, NS(n) = value(n)
time complexity is depth of the tree * max_width of the tree
the only way to check if a given integer array is arithmetic sequence or not is to sort it. Since the sequence has min and max, then it can be sorted by counting sort. The time complexity is O(n), but need extra space.
- runwithfullspeed February 09, 2016One simply need find the the matching of the first row of the 2D pattern, then check if the below rows match the rest pattern or not. The time complexity is n*m, each cell need be touched just once.
- runwithfullspeed February 05, 2016it is a O(n) algorithm.
maxv = sum(A[1] to A[k])
for i = k+1 to n:
tp = maxv - A[i-k] + A[i]
if tp > maxv:
maxv = tp
print maxv
it is a dynamic programming problem.
let B[i][j] be the true/false value if value i can be represented by elements from an array A[1] to A[j]
then B[i][j] = B[i][j-1] or B[i-A[j]][j-1]
B[s/2][n] contain the final result.
It could be solved by counting sort:
1. find the min and max of the elements in the array
2. create any array of size max and init each element to 0
3. use counting sort to get the occurrence of elements in the array
4. check the new array from position min to max, the position of zero are the missing numbers
given A and num:
- runwithfullspeed February 26, 2016