lixulehigh
BAN USER1-D or 2-D space?
- lixulehigh September 28, 2012why not just traverse each list first then add two big numbers up?
- lixulehigh September 28, 2012void quickSort( vector<int> & array)
{
quick(0, array.size(), array)
}
void quick (int begin, int end, vector<int> & array)
{
if (begin == end)
return;
int len = array.size();
// choose the left most as the pivot
int pivot = array[begin];
int j = begin;
for ( int i = 1; i <end;i++)
{
if (pivot > array[i])
{
j++;
swap( array[j], array[i]);
}
}
swap (array[begin], array[j]);
quick(begin, j, array);
quick(j,end,array);
}
- lixulehigh September 27, 2012void mergeSort (vector<int> & Arrary)
{
int len = Arrary.length();
vector<int> workArrary;
for( int blockSize = 1; blockSize < len; blockSize *= 2)
{
for (int blockHead = 0; blockHead<len; blockHead += blockSize)
{
merge(Arrary, blockHead, blockSize, workArrary);
}
}
Arrary = workArrary;
}
merge( vector<int> & Arrary, int blockHead, int blockSize, vector<int> & workArrary)
{
int leftIndex = 0;
int rightIndex = 0;
for (int i = 0; i< 2 * blockSize; i++)
{
if ( leftIndex == blockSize)
{
workArrary[i] = Arrary[blockSize + (rightIndex++)];
continue;
}
if (rightIndex == blockSize)
{
workArray[i] = Arrary[leftIndex++];
continue;
}
workArrary = Arrary[leftIndex]<Arrary[rightIndex]? Arrary[leftIndex++]: Arrary[rightIndex++];
}
}
/* test cases
* 0, 1, 0000000, 10101010,010101, 123456, 654321, -1 -2 -3 -4 -5,
*/
vector<string> permutation (string str)
{
int len = str.length();
vector<bool> used;
used.assign(len, false);
vector<string> result;
string current =””;
addNext (current, used, str, result);
}
void addNext (string current, vector<bool> used, string candidates, vector<string> & result)
{
if(current.size > 0)
result.push_back(current);
int size = used.size();
for (int i = 0; i< size; i++)
{
if (used[i])
continue;
used[i] = true;
addNext(current+candidates, used, candidates, result);
used[i] = false;
}
}
class Node
{
Node* left;
Node* right;
double value;
}
doulbe findClosest (Node * root; double key)
{
vector<double> path;
while (root!=NULL)
{
if(root->value == key)
{return root-> value;}
else if(root->value > key)
{
path.push_back(root -> value);
root = root->left;
continue;
}
else
{
path.push_back(root->value);
root = root -> right;
continue;
}
}
path.push_back(key);
sort(path.begin(), path.end());
int len = path.size();
for (int i = 0; i<len; i++)
{
if (path[i] == key)
{
if (abs(path[i-1]-path[i]) < abs(path[i+1]-path[i]))
return path[i-1];
else
return path[i+1];
}
}
}
- lixulehigh September 26, 2012
use two stacks,
- lixulehigh September 30, 2012push root to A
pop A, print, push left to right children to B, until A is empty
do the same to B
...