Aleksey.M
BAN USERThis is a good observation.
First combinations are obtained as rows and columns in the 2-D array. All other can be obtain as solution for the 'chessmen arrangement on the chessboard' broblem.
But in this case they should be not queens but rooks (beat each other only in vertical and horizontal directions). All other principles are the same.
Start with cur_len = 1 and max_len = 1
Do one pass from 2 to N:
- If (a[i] == 0) then continue with the next iteration (skip a[i] as described in the question)
- else check if((a[i] - a[i-1])*(a[i-1] - a[i-2]) < 0 )
- if yes, then cur_lenght++ and if (cur_len > max_len) max_len = cur_len
- if no, then cur_len = 1 and continue with the next iteration
Unfortunately, the code would not be compiled.
int BSTTree :: kthLarge (BSTNode* start, int k)
{
if (start != NULL)
{
kthLarge (start->right,k);
count ++;
if (count == k)
return start->data;
kthLarge (start->left,k);
// Function must return a value here!!!
}
// Function must return a value here!!!
}
The code below should work for the cases:
- A and B are in the different subtrees
- A or B is LCA
- A and B the same
- there are several nodes with a given values (A and B)
void leastCommonAncestor(Node *pRoot, Node *pA, Node *pB, bool &a_found, bool &b_found, Node **ppLCA)
{
if(!pA || !pB)
{
std::cout << "Error!" << std::endl;
return;
}
if(*ppLCA || !pRoot) return;
if(pRoot->Val == pA->Val) a_found = true;
if(pRoot->Val == pB->Val) b_found = true;
if(!(*ppLCA) && a_found && b_found) /*A and B are the same nodes*/
{
*ppLCA = pRoot;
return;
}
bool a_left_found = false, a_right_found = false, b_left_found = false, b_right_found = false;
leastCommonAncestor(pRoot->pLeft, pA, pB, &a_left_found, &b_left_found, ppLCA);
if(!(*ppLCA))
{
leastCommonAncestor(pRoot->pRight, pA, pB, &a_right_found, &b_right_found, ppLCA);
}
if(!(*ppLCA) && /*in case of there are several given nodes in the tree*/
(a_left_found && b_right_found) || (a_right_found && b_left_found) || /*different subtrees*/
(a_found && (b_left_found || b_right_found)) || (b_found &&(a_left_found || a_right_found))) /*LCA is one of given nodes*/
{
*ppLCA = pRoot;
return;
}
if(!a_found) a_found = a_left_found || a_right_found;
if(!b_found) b_found = b_left_found || b_right_found;
}
That's wrong.
only one person open the door = 1 - 7 / 16 - Prob(nobody opens the door) = 1 - 7 / 16 - 1 / 16 = 8 / 16 = 1 / 2
The same answer can be obtain in the following way:
only one person open the door = Pob(first_person_is_selected) * Prob(first_person_opens_the_door) + .. + Pob(fourth_person_is_selected) * Prob(fourth_person_opens_the_door) = 1/4 * 1/2 + .. +1/4 *1/2 = 1/2
int Source[M][N]; // initial matrix
int Result[M][N]; // matrix with the result
for(int i = 0; i < M; i++) Result[i][0] = Source[i][0];
for(int j = 0; j < N; j++) Result[0][j] = Source[0][j];
for(int i = 1; i < M; i++)
{
for(int j = 1; j < N; j++)
{
if(Source[i][j] == 0)
{
Result[i][j] = Source[i][j];
}
else
{
Result[i][j] = min(Result[i - 1][j], Result[i][j - 1], Result[i - 1][j - 1]) + 1;
}
}
}
Now let's Result[i_max][j_max] is the largest value in the Result matrix. Then (i_max, j_max) - indexes of the bottom right corner of the answer submatrix, and Result[i_max][j_max] is the size (dimention) of the answer submatrix.
I.e., the answer of the question is a submatrix of the Source matrix Source[i_max - Result[i_max][j_max] + 1 .. i_max][j_max - Result[i_max][j_max] + 1 .. j_max].
Good. If we also change an order of checks in the algo as following, the algo outputs data in increasing order:
if(node.data > r2)
printRange(node.left, r1, r2);
if(r1 <= node.data && node.data <= r2) {
System.out.println("Node data: " + node.data);
printRange(node.left, r1, r2);
printRange(node.right, r1, r2);
}
if(node.data < r1)
printRange(node.right, r1, r2);
From my perspective the right answer here is that Hashtables and Arrays can only be based on continues memory block (Even in case of chaining collision resolution in Hashtables heads of lists are stored in an array).
While Dictionaries, Trees and Linked Lists CAN be implemented using both Arrays (continues memory) (which is not usual case) and fragmented memory (usual case).
Comments?
I think this is a right solution. My only proposal for improvement not to do straight forward iterating but go by perimeter: top,left to top,right; top,right to bottom,right; bottom,right to bottom,left and, finally, bottom,left to the top,left. Then just decrease each grid dimension by one and continue iterating.
- Aleksey.M May 27, 2013Improvement here is that we stop exactly at the moment we have processed each side of the target minimum rectangular.