Ethan
BAN USERvoid generateOdd(int n, vector<int> &result)
{
if ( n == 0 )
{//print result
int len = result.size();
for ( int i = 0; i<len-1; i++)
cout<<result[i]<<"+";
cout<<result[len-1]<<endl;
}
int min = n;
if ( result.empty() == false )
min = *(result.end() - 1);
for ( int j = n > min ? min : n; j>0; j--)
{
if ( (j & 0x1) == 0 )
continue;
if ( n - j > -1 )
{
result.push_back(j);
generateOdd(n-j, result);
result.pop_back();
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
vector<int> res;
generateOdd(11, res);
return 0;
}
Explain time cost:
assume average everyone know k person, like k=n/2.
so first loop, vec[] size will be k=n/2, and first person and second person both know will be n/4; three person common know will be n/8, and so on n/16, n/32.
so first loop, time use is n,
and second n/2.
third n/4.... so total is n + n/2 + n/4 + n/8..... = 2*n;
if k != n/2, let it k = n *q(q < 1 it's obvious.
so first loop tile is n,
second n*q,
third n*q*q.
so total = n + n*q + n*q*q + ... = n + n / (1 - q ) = n * ( 1 + 1 / (1-q)).
vector<people> vec;
for (int i=1; i<n; i++)
{
if ( know (person[0], person[i]) is true)
add i to vec.
}
if (vec.size() == n - 1)
person[0] is head, end.
for ( int i=1; i<n; i++)
{
for (int j=0; j<vec.size(); j++ )
{
if ( know(person[i], vec[j] ) == false )
vec.erase(j);
if ( vec.size() == 0)
{
stop, vec[0] is head.
}
}
}
space O(n), time O(n) too.
int findFirstOne(int *arr, int len)
{
if ( arr == NULL || len < 1 )
return -1;
if ( arr[0] == 1 ) // if array order is decreese, first item is answer.
return 0;
//binary search.
int i=0;
int j = len - 1;
while ( i < j)
{
int mid = i + (j-i)/2;
if ( arr[mid] == 1)
{
j = mid;
}
else
{
i = mid+1;
}
}
return arr[j] ? j : -1; // if this array don't have 1, return -1.
}
Bubble Sort, with O(n^2) time complexity, I think without additional memory, this is best solution, and use isSorted and pEnd to reduce complexity too.
struct Node
{
Node *next;
int value;
};
Node* BubbleSortList(Node *pHead)
{
if ( pHead == NULL || pHead->next == NULL ) // Empty or only one node case.
return pHead;
bool isSorted = false;
Node *pEnd = NULL; // point to last loop sorted item.
Node *pLastSwapNode = NULL;
while (pEnd != pHead && isSorted == false)
{
isSorted = true;
Node *pCurrent = pHead;
while (pCurrent->next != pEnd)
{
if (pCurrent->value > pCurrent->next->value )
{
swap(pCurrent->value, pCurrent->next->value); // don't swap node, just swap its value.
isSorted = false;
pLastSwapNode = pCurrent->next; // record swap last node.
}
pCurrent = pCurrent->next;
}
pEnd = pLastSwapNode;
}
return pHead;
}
void permutations(vector<int> &vec,int i)
- Ethan April 25, 2012{
if ( i == vec.size() )
{
copy(vec.begin(), vec.end(), ostream_iterator<int>(cout," "));
cout<<endl;
return;
}
for (int j=i; j<vec.size(); j++)
{
swap(vec[i],vec[j]);
permutations(vec, j+1);
swap(vec[i], vec[j]);
}
}
void test1()
{
int arr[] = {1,2,3,4};
vector<int> vec(arr,arr+4);
permutations(vec, 0);
}