wangxuyang
BAN USERhowever, negative integers should not be ignored.
- wangxuyang March 04, 2013ideone.com/57nnb
- wangxuyang October 17, 2012ideone.com/57nnb is a C code for this question. I also use a swap counter.
- wangxuyang October 17, 2012post-suffix or manacher, O(n)
- wangxuyang October 08, 2012O(logN) instead of O(N)
NodeType* getSecondMax(NodeType* root)
{
if(root == NULL)
{
return NULL;
}
NodeType* pre = NULL;
NodeType* max = root;
while(max->r)
{
pre = max;
max = max->r;
}
if(pre == NULL)
{
if(root->l == NULL)
{
return NULL;
}
else
{
return rightMostNode(root->l);
}
}
else if(pre->l == NULL)
{
return pre;
}
else
{
return rightMostNode(pre);
}
}
ideone.com/m5fPS
#include <stdio.h>
#include <string.h>
const int MaxSize = 1000;
int data[MaxSize + 1];
int getMax(int a, int b){return a > b ? a : b;}
int getMin(int a, int b){return a < b ? a : b;}
int GetMaxPro(int *data, int n)
{
int max = 1;
int min = 1;
int ret = 0;
for(int i = 0; i < n; i ++)
{
if(data[i] > 0)
{
max = max * data[i];
min = getMin(min * data[i], 1);
}
else if(data[i] == 0)
{
max = 1;
min = 1;
}
else /* data[i] < 0 */
{
max = getMax(min * data[i], 1);
min = getMin(min * data[i], data[i]);
}
ret = getMax(ret, max);
}
return ret;
}
int main()
{
int n;
while(scanf("%d", &n) == 1)
{
for(int i = 0; i < n; i++)
{
scanf("%d", &data[i]);
}
int ret = GetMaxPro(data, n);
printf("ret = %d\n", ret);
}
return 0;
}
you just written a zero-one pack, for this question:
for(house = houseA to houseC)
{
for(days = 0 to 15)
{
dp[days] = max(dp[days - house.day] + house.value, dp[days]);
}
}
quick select alg is ok for that.
- wangxuyang September 25, 2012recursive way
NodeType* reverse(NodeType* head)
{
if(root == NULL || head->next == NULL) return root;
NodeType* newHead = reverse(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
DFS
NodeType* findLCA(NodeType* root, NodeType* e1, NodeType* e2)
{
if(root == NULL) return NULL;
if(root == e1 || root == e2) return root;
NodeType* lRet = findLCA(root->l, e1, e2);
NodeType* rRet = findLCA(root->r, e1, e2);
if(lRet && rRet) return root;
if(!lRet) return rRet;
return lRet;
}
great code, last->previous. and works on a tree of multi-levels.
- wangxuyang September 25, 2012great code. but you forget to take off the additional zeros.
101 * 101 = 10201
here is a none recursive way:
unsigned int calc(unsigned int a, unsigned int b)
{
unsigned int tmp = a;
unsigned int ret = 1;
while(b)
{
if(b & 1)
{
ret *= tmp;
}
tmp *= tmp;
b >>= 1;
}
return ret;
}
O(N),first pass we just deal 1 to make the string shorter from the start to the end, second pass we deal others to make the string longer from the end to the start.
- wangxuyang March 04, 2013