speedmancs
BAN USERThat transformation is incorrect, consider the original array is {1,2}, after putting netative numbers , it will be {1,2,-1,-2}, for target 1, there will be three combinations : 1, 2 + (-1), 1 + 2 + (-2), while in the original array, there are only two combinations: 1 and 2 + (-1). They are not equivalent.
- speedmancs March 16, 2013a quick sort version
#include <iostream>
#include <iterator>
#include <algorithm>
#include <cmath>
using namespace std;
void Swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}
void QuickSort(int * a, int beg, int step, int end, bool bAsc)
{
int n = ceil( (end - beg) / step);
if (n ==0 || n == 1 || n < 0)
return;
int v = a[beg];
int i = beg + step;
int j = i;
// the invariation is a[beg:i) <= v and a[i:j) > v and a[j:end) are unknown
while (j < end)
{
if ((a[j] > v && bAsc) || (a[j] < v && !bAsc))
{
j += step;
}
else
{
Swap(a + j, a + i);
j += step;
i += step;
}
}
Swap(a + beg, a + i - step);
QuickSort(a, beg, step, i - step, bAsc);
QuickSort(a, i, step, end, bAsc);
}
int main(int argc, char **argv)
{
int a[] = {3, 6, 7, 8, 1, 4, 2, 4, 6, 8, 10};
int n = sizeof(a) / sizeof(int);
QuickSort(a, 0 , 2, n, true);
QuickSort(a, 1, 2, n, false);
copy(a, a + n, ostream_iterator<int>(cout, " "));
cout << endl;
return 0;
}
I have written a quick sort version, the function signature is as the following
void QuickSort(int * a, int beg, int step, int end, bool bAsc).
1. you can unify insertion_srtEven and insertion_srtOdd into a single function which is better and easier for maintainment
2. the average time complexity of insert sort is also O(n^2) while the best average complexity of sorting is O(nlgn)
In this way, all your elements will be positive, which may violate the input
- speedmancs February 17, 2013bool Match(const string& str)
{
stack<char> s;
for (string::const_iterator it = str.begin();
it != str.end(); it++)
{
if (s.empty())
{
s.push(*it);
continue;
}
char c = s.top();
if ((*it == ']' && c == '[') ||
(*it == '}' && c == '{') ||
(*it == ')' && c == '('))
{
s.pop();
}
else{
s.push(*it);
}
}
return s.empty();
}
initially, the stack is empty, so when you encounter "}", your program will crash because the empty stack couldn't pop anything out
- speedmancs January 28, 2013#include <iostream>
#include <vector>
using namespace std;
class TreeNode
{
public:
TreeNode(int _v, TreeNode * _left, TreeNode * _right)
{
v = _v;
left = _left;
right = _right;
}
int v;
TreeNode * left;
TreeNode * right;
};
class BST
{
public:
BST()
{
root = NULL;
}
BST(int * a, int n);
~BST();
TreeNode * Insert(int v);
TreeNode * Search(int v);
TreeNode * Successor(TreeNode * node);
void Print();
bool Find(TreeNode * node, vector<TreeNode* >& ancestors);
private:
void Release(TreeNode *node);
void Print(TreeNode * node);
TreeNode * root;
};
bool BST::Find(TreeNode * node, vector<TreeNode*>& ancestors)
{
if (node == NULL)
return false;
int v = node->v;
ancestors.clear();
if (root == NULL)
return false;
TreeNode * cur = root;
while (cur != NULL)
{
if (v < cur->v)
{
ancestors.push_back(cur);
cur = cur->left;
continue;
}
if (v > cur->v)
{
ancestors.push_back(cur);
cur = cur->right;
continue;
}
// v == cur->v
if (cur == node)
break;
ancestors.push_back(cur);
cur = cur->right;
}
return cur == node;
}
TreeNode * BST::Search(int v)
{
TreeNode * cur = root;
while (cur != NULL && cur->v != v)
{
if (v < cur->v)
cur = cur->left;
else if (v > cur->v)
cur = cur->right;
}
//cur == NULL or cur->v == v
return cur;
}
TreeNode * BST::Successor(TreeNode * node)
{
TreeNode * successor = NULL;
if (node == NULL)
return NULL;
// if node has right child
// then successor is its leftmost descendent
if (node->right != NULL)
{
successor = node->right;
TreeNode * cur = node->right->left;
while (cur != NULL)
{
successor = cur;
cur = cur->left;
}
return successor;
}
//if node has no right child
vector<TreeNode *> ancestor;
bool bSuc = Find(node, ancestor);
if (!bSuc)
return NULL;
ancestor.push_back(node);
int n = ancestor.size();
for (int i = n - 2; i >= 0; i--)
{
if (ancestor[i]->left == ancestor[i + 1])
{
successor = ancestor[i];
break;
}
}
return successor;
}
BST::BST(int *a, int n)
{
root = NULL;
for (int i = 0; i < n; i++)
{
Insert(a[i]);
}
}
BST::~BST()
{
Release(root);
}
void BST::Release(TreeNode * node)
{
if (node == NULL)
return;
Release(node->left);
Release(node->right);
delete node;
}
/*
left: less than
right: great than or equal to
middle: equal to
*/
TreeNode * BST::Insert(int v)
{
//if the tree is empty
if (root == NULL)
{
root = new TreeNode(v, NULL, NULL);
return root;
}
TreeNode * parent = NULL;
TreeNode * cur = root;
while (cur != NULL)
{
if (v < cur->v)
{
parent = cur;
cur = cur->left;
continue;
}
if (v >= cur->v)
{
parent = cur;
cur = cur->right;
continue;
}
}
//now cur is NULL, its parent is parent
TreeNode * node = new TreeNode(v, NULL, NULL);
if (v < parent->v)
parent->left = node;
if (v >= parent->v)
parent->right = node;
return node;
}
void BST::Print()
{
Print(root);
}
void BST::Print(TreeNode * node)
{
if (node == NULL)
return;
Print (node->left);
cout << node->v << " ";
Print (node->right);
}
int main(int argc, char ** argv)
{
int a[] = {2, 4, 6, 7, 5, 9, 10, 9, 8, 8, 2};
// 2 2 4 5 6 7 8 8 9 9 10
BST tree(a, sizeof(a) / sizeof(int));
tree.Print();
cout << endl;
TreeNode * node = tree.Search(2);
while (node != NULL)
{
cout << node->v << " ";
node = tree.Successor(node);
}
cout << endl;
//TreeNode * sucNode = tree.Successor(node);
//cout << sucNode->v << endl;
return 0;
}
It matters, given the point to some Node, you should find its parent node where value repetition of nodes matters.
- speedmancs January 28, 2013bool IsSet(int * a, int n)
{
int t = 0;
while (t < n)
{
if (a[t] <= 0)
return false;
if (t == 0)
continue;
if (a[t] <= a[t - 1])
return false;
t++;
}
return true;
}
void Multipy(int a[4], int b[4], int c[4])
{
c[0] = a[0] * b[0] + a[1] * b[2];
c[1] = a[0] * b[1] + a[1] * b[3];
c[2] = a[2] * b[0] + a[3] * b[2];
c[3] = a[2] * b[1] + a[3] * b[3];
}
void Exp(int a[4], int b[4], int n)
{
if (n == 1)
{
memcpy(b, a, sizeof(int) * 4);
return;
}
if (n == 0)
{
b[0] = b[3] = 1;
b[1] = b[2] = 0;
return;
}
int half_n = int(n / 2);
int c[4];
Exp(a, c, half_n);
int c2[4];
Multipy(c, c, c2);
if (n % 2 == 1)
{
Multipy(c2, a, b);
}
else{
for (int i = 0; i < 4; i++)
b[i] = c2[i];
}
}
int main(int argc, char ** argv)
{
if (argc < 2)
return 0;
int n = atoi(argv[1]);
int a[4] = {2, 2, 1, 0};
int b[4];
Exp(a, b , n - 1);
int fn = b[0] + b1 / 2; // b1 must be even number, cause fn is a integer
cout << fn << endl;
return 0;
}
void Merge(int * a, int m, int * b, int n, vector<int>& c)
{
int p = 0; int q = 0;
while (p < m && q < n)
{
if (a[p] < b[q])
{
c.push_back(a[p++]);
}
else if (a[p] > b[q])
{
c.push_back(b[q++]);
}else
{
c.push_back(a[p++]);
q++;
}
}
while (p < m)
{
c.push_back(a[p++]);
}
while (q < n)
{
c.push_back(b[q++]);
}
}
char * p = "aaaaabbbbbbbbbbbbbbefxsscc";
int len = strlen(p);
cout << len << endl;
int idx = 0;
int maxRep = 0;
int maxIdx = 0;
while (idx < len)
{
int nRep = 1;
int idx2 = idx + 1;
while (idx2 < len && p[idx2] == p[idx])
{
idx2 ++;
nRep ++;
}
if (nRep > maxRep)
{
maxRep = nRep;
maxIdx = idx;
}
idx = idx2;
}
cout << "maxRep:" << maxRep << " maxIdx:" << maxIdx << endl;
it's easy to see nt^k = mt
- speedmancs June 02, 2011suppose we are seeking for log(n,m), let k = log(n,m) which is what we are looking for.
then we have n^k = m. we can introduce a variable t and let
nt = n^((1/2)^t)
mt = m^((1/2)^t)
it means we call sqrt(n) and sqrt(m) t times.
It's easy to see nt^k = mt.
And we suppose n > 1 (if n < 1 we can let n' = 1/n, and log(n,m) = -log(n',m))
So we have nt > 1, let nt = 1 + a,when t increase,the limit of a will be 0.
and we have (1 + a)^k nearly equal to 1 + ka. put them together,we have
(1 + ka) equal to mt
=> k = (mt - 1) / a => k = (mt - 1) / (nt - 1)
- speedmancs March 16, 2013