euv921
BAN USERI used the algorithm of the 0-1 knapsack problem.
pair<vector<int>,int> findMinCost(const int* coinDenoms,
const int coinDenomSize, const int* coinCost, const int coinCostSize,
const int amount, const int limitPerDenomination) {
vector<int> empty;
pair<vector<int>,int> wrongpair = make_pair(empty,-1);
pair<vector<int>,int> emptypair = make_pair(empty,0);
if (coinDenomSize!=coinCostSize) return wrongpair;
if (amount==0) return emptypair;
if (limitPerDenomination==0) return wrongpair;
if (coinDenomSize==0) return wrongpair;
if (coinDenoms[coinDenomSize-1]>amount)
return findMinCost(coinDenoms,coinDenomSize-1,coinCost,
coinCostSize-1,amount,limitPerDenomination);
pair<vector<int>,int> temp1=findMinCost(coinDenoms,coinDenomSize-1,
coinCost,coinCostSize-1,amount,limitPerDenomination);
pair<vector<int>,int> temp2=findMinCost(coinDenoms,coinDenomSize,
coinCost,coinCostSize,amount-coinDenoms[coinDenomSize-1],limitPerDenomination-1);
if (temp1.second==-1&&temp2.second==-1)
return wrongpair;
else if (temp1.second==-1) {
temp2.first.push_back(coinCost[coinCostSize-1]);
temp2.second+=coinCost[coinCostSize-1];
return temp2;
}
else if (temp2.second==-1)
return temp1;
else {
temp2.first.push_back(coinCost[coinCostSize-1]);
temp2.second+=coinCost[coinCostSize-1];
return (temp1.second<temp2.second ? temp1:temp2);
}
}
Assume the return value is temp of type pair<vector<int>,int>.
Then, the findMinCost() array would be temp.first.
void directory(char * &str) {
int len = strlen(str);
char * traverse = str+len-1;
char * copyTo = str+len-1;
while (traverse>=str) {
while (*traverse=='.') {
int flag = 0;
while (*traverse=='.' || *traverse=='\\') {
if (*traverse=='\\')
flag++;
traverse--;
}
while (flag!=0) {
if (*traverse=='\\')
flag--;
traverse--;
}
}
*copyTo = *traverse;
traverse--;
copyTo--;
}
copyTo++;
str = copyTo;
}
I think the problem is you missed the case when A[mid]==key.
Here is the fix:
int BsearchStartIndex( int *A, int start, int end, int key )
{
int mid = ( start + end )/2;
if( (start == end ) )
{
if( (A[mid] == key) )
{
return start;
}
else
{
return -1; // key not exists
}
}
else if( A[mid] < key )
{
start = mid +1 ;
}
else if( A[mid] > key)
{
end = mid -1;
}
else // A[mid] == key
{
if (A[mid-1] != A[mid])
return mid;
}
return BsearchStartIndex( A, start, end, key );
}
int BSearchEndIndex( int *A, int start, int end , int key )
{
int mid = ( start + end )/2;
if( (start == end ))
{
if( (A[mid] == key) )
{
return end;
}
else
{
return -1; // key not exists
}
}
else if( A[mid] > key )
{
end = mid -1 ;
}
else if( A[mid] < key )
{
start = mid +1 ;
}
else
{
if ( A[mid] != A[mid+1])
return mid;
}
return BsearchStartIndex( A, start, end, key );
}
int main()
{
startIndex = BsearchStartIndex( A, 0, n-1, key );
if (startIndex == -1) endIndex = -1;
else
endIndex = BsearchEndIndex( A, startIndex, n-1, key );
}
char* findSecLargest (string const &str) {
char * cstr = (char *) malloc ((str.length()+1) * sizeof(char));
strcpy (cstr, str.c_str());
char * largest = "";
char * secLargest = "";
char * p = strtok (cstr, " .,\?!\"\'");
while (p != NULL) {
if (strlen(p)>strlen(largest)) {
secLargest = largest;
largest = p;
}
else if (strlen(p)>strlen(secLargest)) {
secLargest = p;
}
p = strtok (NULL, " .,\?!\"\'");
}
return secLargest;
}
I don't think "if(root->next->next == NULL)" is necessary, since you already considered when root->next == NULL.
so the code would be:
void reverse_LL(*root, *head)
{
if(root == NULL || root->next == NULL)
{
head = root;
return;
}
reverse(root->next, head);
root->next->next = root;
root->next = NULL;
}
I use only one parameter, instead of two. see if it is correct.
void reverseTree(node*root){
if(root!=NULL){
reverseTree(root->left);
reverseTree(root->right);
root->left->left=root;
root->left->right=root;
root->right->right=root;
root->right->left=root;
}
}
Initial call will be reverseTree(root).
Another way without bitwise operations:
- euv921 September 19, 2011