remlostime
BAN USERit works, thanks for your code. But next time, you can explain more your code. Then it makes our life easy.
- remlostime November 09, 2012That's really fucking cool!
- remlostime November 08, 2012sort the query array O(klogk). from left to find the array in query, and fron right to find the array in query. O(nlogk).
We also can put the array in hash, and the find will just take O(n)
This is a creative method when someone used to interview with google a few years ago. Finally, the interviewer says this is really a great method, and he got the offer!!!
- remlostime November 05, 2012convert the BST to doubly linked list, O(n) for two trees. Compare the link list, O(n)
- remlostime November 05, 2012DP solves it in O(n * n * K).
int solve(int a[], int size, int K)
{
int f[100][100];
memset(f, 0, sizeof(f));
for(int i = 0; i < size; i++)
f[i][1] = 1;
for(int i = 1; i < size; i++)
for(int j = 0; j < i; j++)
if (a[i] > a[j])
for(int k = 1; k <= K - 1; k++)
f[i][k+1] += f[j][k];
int sum = 0;
for(int i = 0; i < size; i++)
sum += f[i][K];
return sum;
}
int main()
{
int a[] = {1, 4, 6, 2, 5};
int K = 3;
cout << solve(a, sizeof(a) / sizeof(int), K) << endl;
}
DP solve it.
#include <iostream>
using namespace std;
int main()
{
int f[10];
f[0] = 1;
f[1] = 2;
for(int i = 2; i < 10; i++)
f[i] = f[i-1] + f[i-2];
int sum[10][100];
int size = 0;
int N = 13;
while(size < 10)
{
if (f[size] <= N)
size++;
else
break;
}
memset(sum, 0, sizeof(sum));
for(int i = 0; i < size; i++)
{
sum[i][f[i]] = 1;
for(int j = 0; j < i; j++)
for(int k = 1; k <= N - f[i]; k++)
sum[i][k + f[i]] += sum[j][k];
}
int ret = 0;
for(int i = 0; i < size; i++)
ret += sum[i][N];
cout << ret << endl;
}
the most important thing there is if we can think the first element is the answer in the problem, like the sequence is 0 1, and 0 <= 1, but there is no element before 0, could we think 0 is the answer. If yes, then the algo given by the author is right, else it's wrong.
- remlostime November 01, 2012Hi, friend. If the node has no parent, your code cannot work. So could you try one version that has no parent. And the time complexity is still O(n + m)
- remlostime October 22, 2012#include <iostream>
using namespace std;
int main()
{
int f[100][100];
int X = 3;
int Y = 2;
memset(f, 0, sizeof(f));
const int aSize = 4;
string a[aSize] = {"01", "10", "0", "110"};
for(int i = 0; i < aSize; i++)
{
int zeroNum = 0;
int oneNum = 0;
for(int j = 0; j < a[i].size(); j++)
if (a[i][j] == '1')
oneNum++;
else
zeroNum++;
for(int x = X; x >= 0; x--)
for(int y = Y; y >= 0; y--)
{
int preX = x - zeroNum;
int preY = y - oneNum;
if (preX >= 0 && preY >= 0 && (f[preX][preY] > 0 || (preX == 0 && preY == 0)))
f[x][y] = max(f[x][y], f[preX][preY] + 1);
}
}
cout << f[X][Y] << endl;
}
O(nlogn)
struct Node
{
int index;
int val;
Node(int idx, int v):index(idx), val(v){}
Node(){}
};
struct Pair
{
int i;
int j;
Pair(){}
Pair(int _i, int _j):i(_i), j(_j){}
};
Node c[1000];
Pair mergeSort(vector<Node> &a, int left, int right)
{
if (left >= right)
{
return Pair(0, -1);
}
int mid = (left + right) / 2;
Pair pLeft = mergeSort(a, left, mid);
Pair pRight = mergeSort(a, mid + 1, right);
Pair p;
int i = INT_MAX;
int j = INT_MIN;
p.i = i;
p.j = j;
int index1 = left;
int index2 = mid + 1;
int index = left;
while(index1 <= mid && index2 <= right)
{
if (a[index1].val <= a[index2].val)
{
c[index] = a[index1++];
}
else
{
c[index] = a[index2++];
}
j = c[index].index;
if (i == INT_MAX || j - i > p.j - p.i)
{
p.j = j;
p.i = i;
}
i = min(c[index].index, i);
index++;
}
while(index1 <= mid)
{
c[index] = a[index1++];
j = c[index].index;
if (i == INT_MAX || j - i > p.j - p.i)
{
p.j = j;
p.i = i;
}
i = min(c[index].index, i);
index++;
}
while(index2 <= right)
{
c[index] = a[index2++];
j = c[index].index;
if (i == INT_MAX || j - i > p.j - p.i)
{
p.j = j;
p.i = i;
}
i = min(c[index].index, i);
index++;
}
for(int i = left; i <= right; i++)
a[i] = c[i];
if (pLeft.j - pLeft.i > p.j - p.i)
p = pLeft;
if (pRight.j - pRight.i > p.j - p.i)
p = pRight;
return p;
}
#include <iostream>
#include <cmath>
using namespace std;
struct Node
{
Node *left;
Node *right;
double val;
Node():left(NULL), right(NULL){}
};
Node *find(Node *node, double key)
{
if (node == NULL)
return NULL;
double val = node->val;
if (val == key)
return node;
else if (val < key)
{
Node *ret = find(node->right, key);
if (ret == NULL)
return node;
else
return abs(node->val - key) < abs(ret->val - key) ? node : ret;
}
else
{
Node *ret = find(node->left, key);
if (ret == NULL)
return node;
else
return abs(node->val - key) < abs(ret->val - key) ? node : ret;
}
}
int main()
{
Node node[10];
for(int i = 0; i < 10; i++)
node[i].val = i;
node[4].left = &node[2];
node[4].right = &node[7];
node[2].left = &node[1];
node[2].right = &node[3];
node[1].left = &node[0];
node[7].left = &node[6];
node[7].right = &node[8];
node[6].left = &node[5];
node[8].right = &node[9];
Node *ret = find(&node[4], 4);
cout << "key:" << 4 << " ret:" << ret->val << endl;
ret = find(&node[4], 4.4);
cout << "key:" << 4.4 << " ret:" << ret->val << endl;
ret = find(&node[4], 10);
cout << "key:" << 10 << " ret:" << ret->val << endl;
ret = find(&node[4], 1.1);
cout << "key:" << 1.1 << " ret:" << ret->val << endl;
ret = find(&node[4], -1);
cout << "key:" << -1 << " ret:" << ret->val << endl;
ret = find(&node[3], 3.3);
cout << "key:" << 3.3 << " ret:" << ret->val << endl;
}
#include <iostream>
#include <set>
#include <string>
using namespace std;
void print(int index, int f[], string &s)
{
if (index == 0)
return;
print(f[index], f, s);
string a(s, f[index], index - 1 - f[index] + 1);
if (f[index] != 0)
cout << ' ' << a;
else
cout << a;
}
int main()
{
int f[1000]; // record the previous successful sentence index, if -1 not success
string s = "Googleisawesome";
set<string> word;
word.insert("Google");
word.insert("is");
word.insert("awesome");
f[0] = 0;
for(int i = 1; i <= s.size(); i++)
{
f[i] = -1;
for(int j = 0; j <= i - 1; j++)
if (f[j] != -1)
{
int startIndex = j;
int endIndex = i - 1;
string a(s, startIndex, endIndex - startIndex + 1);
if (word.count(a)) // find one solution
{
f[i] = j;
break;
}
}
}
if (f[s.size()] == -1)
cout << "no answer" << endl;
else
print(s.size(), f, s);
}
it's correct! Really awesome solution.
- remlostime October 21, 2012it's correct answer. but i am really wonder if we could implement so complex data structure in such a short time!!!!! Is it possible? and interval tree is easy to write with bugs. Could we use a simpler data struct and get a good time complexity.
- remlostime October 19, 2012O(n^3) = no hire
- remlostime October 19, 2012Node *findNextNode(Node *node)
{
if (node == NULL)
return NULL;
if (node->right)
{
Node *p = node->right;
while(p->left)
p = p->left;
return p;
}
else
{
Node *parent = node->parent;
while(parent && parent->right == node)
{
node = parent;
parent = parent->parent;
}
return parent;
}
}
Not correct.
for example: 6 1
your result is: 1 1. cost 5
but we can delete 1, and result is: 6. cost 1
DP problem. can be solved in O(n*n).
#include <iostream>
using namespace std;
int main()
{
int f[100];
int newA[100];
int a[100] = {3, 2, 4, 1};
int n = 4;
a[n] = INT_MAX;
f[n] = 0;
newA[n] = INT_MAX;
for(int i = n - 1; i >= 0; i--)
{
f[i] = INT_MAX;
for(int j = i + 1; j <= n; j++)
if (a[i] > newA[j])
{
int sum = 0;
for(int k = i + 1; k < j; k++)
sum += a[k];
if (f[j] + sum + a[i] - newA[j] < f[i])
{
f[i] = f[j] + sum + a[i] - newA[j];
newA[i] = newA[j];
}
}
else
{
int sum = 0;
for(int k = i + 1; k < j; k++)
sum += a[k];
if (f[j] + sum < f[i])
{
f[i] = f[j] + sum;
newA[i] = a[i];
}
}
}
cout << f[0] << endl;
}
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
- remlostime October 05, 2012void delSlash(char *s)
{
if (s == NULL)
return;
int i = 1;
int j = 1;
int len = strlen(s);
if (len == 0)
return;
while(j < len)
{
if (s[j] == '/' && s[i-1] == '/')
j++;
else
{
s[i] = s[j];
i++;
j++;
}
}
s[i] = '\0';
}
- remlostime November 26, 2012