hwen.tmp
BAN USER#include <algorithm>
static void _print_arr(const int A[], int N)
{
std::cout << '[' << A[0] << std::endl;
for(int i = 0; i < N; i++)
std::cout << ',' << A[i];
std::cout << ']' << std::endl;
}
void static _print_combination(int A[], int k, int N)
{
if(k == N)
{
_print_arr(A, N);
return;
} // if
_print_combination(A, k + 1, N);
for(int i = k + 1; i < N; i++)
{
if(A[i] != A[k])
{
std::swap(A[k], A[i]);
_print_combination(A, i, N);
std::swap(A[k], A[i]);
}
} // for
} // _print_combination
void print_combination(const int A[], int N)
{
int* A2 = new int[N];
std::copy(A, A + N, A2);
std::sort(A2, A2 + N);
_print_combination(A2, 0, N);
} // print_combination
int main(void)
{
int A[] = {1, 2, 1};
print_combination(A, sizeof(A) / sizeof(A[0]));
return 0;
}
#include <stack>
typedef struct node_targ
{
int data;
struct node_targ *left;
struct node_targ *right;
} node;
typedef node* BTree;
void print_btree_breadth(const BTree &tree)
{
deque<node *> level;
stack<node *> round;
level.push_front(tree);
while(level.size() != 0)
{
node *cur = level.front();
level.pop_front();
round.push(cur);
if(cur->right != NULL)
level.push_back(cur->right);
if(cur->left != NULL)
level.push_back(cur->left);
} // while
while(round.size() != 0)
std::cout << '[' << round.top()->data << ']' << std::endl , round.pop();
} // print_btree_breadth
int main(void)
{
node n7 = {7, NULL, NULL};
node n6 = {6, NULL, NULL};
node n5 = {5, NULL, NULL};
node n4 = {4, NULL, NULL};
node n3 = {3, &n6, &n7};
node n2 = {2, &n4, &n5};
node n1 = {1, &n2, &n3};
BTree tree = &n1;
print_btree_breadth(tree);
return 0;
}
O(N^2)
bool find_3_num(const int A[], int N, int X[])
{
assert(N >= 3 && X != NULL && A != NULL);
int *A2 = new int[N];
// memcpy(A2, A, N * sizeof(int));
//qsort(A2, N, sizeof(int), compare);
copy(A, A + N, A2);
sort(A2, A2+N);
for(int k = 0; k < N - 2; ++k)
{
int i = k+1, j = N - 1;
while(i < j)
{
int sum = A2[k] + A2[i] + A2[j];
if(sum == 0)
{
X[0] = A2[k], X[1] = A2[k+1], X[2] = A2[k+2];
return true;
}
else if(sum < 0)
{
i++;
}
else
{
j--;
}
} // while
}
return false;
}
int main(void)
{
int A[] = {1, 2, 4, -3, 9};
int X[3];
find_3_num(A, sizeof(A) / sizeof(A[0]), X);
return 0;
}
- hwen.tmp September 06, 2012