wenlei.zhouwl
BAN USERBinary search
#include <iostream>
using namespace std;
struct node{
int time;
int val;
};
int findpos(node *nodes, int n, int k)
{
int start = 0;
int end = n - 1;
if (start == end)
{
return start;
}
while (end > start + 1)
{
int mid = start + (end - start) / 2;
if (k > nodes[mid].time)
{
start = mid;
} else if (k < nodes[mid].time)
{
end = mid - 1;
} else
{
start = mid;
}
}
if (nodes[end].time == k)
{
return end;
}
if (nodes[end].time < k)
{
if (end + 1 == n)
{
return n - 1;
}
if (nodes[end + 1].time - k > k - nodes[end].time)
{
return end;
}
return end + 1;
}
if (start == -1)
{
return 0;
}
if (nodes[start].time == k)
{
return start;
}
if (nodes[start + 1].time - k > k - nodes[start].time)
{
return start;
}
return start + 1;
}
int main()
{
int n, k;
node A[100];
cin >> n >> k;
for (int i = 0; i < n; ++i)
{
cin >> A[i].time >> A[i].val;
}
int pos = findpos(A, n, k);
cout << A[pos].time << " " << A[pos].val << endl;
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct node
{
int start;
int end;
};
bool cmp(node a, node b)
{
if (a.end <= b.end)
{
return true;
}
return false;
}
void maxjob(vector<node> jobs)
{
sort(jobs.begin(), jobs.end(), cmp);
vector<node>::iterator iter;
iter = jobs.begin();
int t = iter->end;
cout << iter->start << " " << iter->end << endl;
++iter;
for (; iter != jobs.end(); ++iter)
{
if (t <= iter->start)
{
cout << iter->start << " " << iter->end << endl;
t = iter->end;
}
}
}
int main()
{
int n;
vector<node> jobs;
cin >> n;
while (n--)
{
node job;
cin >> job.start >> job.end;
jobs.push_back(job);
}
maxjob(jobs);
return 0;
}
Here is the code in c++:
#include <iostream>
using namespace std;
void swap(int A[], int i, int j)
{
A[i] ^= A[j];
A[j] ^= A[i];
A[i] ^= A[j];
}
void move(int A[], int to, int from)
{
for (int i = from - 1; i >= to; --i)
{
swap(A, i, i + 1);
}
}
void max(int A[], int n)
{
int limit = n;
for (int i = 0; i < n; ++i)
{
int pos = i;
for (int j = 1; i + j < n && j <= limit; ++j)
{
if (A[pos] < A[i + j])
{
pos = i + j;
}
}
limit -= pos - i;
move(A, i, pos);
}
}
int main()
{
int A[100];
int m, n;
cin >> m >> n;
for (int i = 0; i < m; ++i)
{
cin >> A[i];
}
max(A, n);
for (int i = 0; i < m; ++i)
{
cout << A[i] << " ";
}
cout << endl;
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
void increase(vector<int> &value)
{
vector<int>::iterator iter;
for (iter = value.begin(); iter != value.end(); ++iter)
{
if (*iter < 9)
{
++*iter;
break;
}
else
{
*iter = 0;
}
}
if (iter == value.end())
{
value.push_back(1);
}
iter = value.end() - 1;
for (; iter >= value.begin(); --iter)
{
cout << *iter;
}
cout << endl;
}
int main()
{
vector<int> value;
string s;
cin >> s;
for (int i = s.size() - 1; i >= 0; --i)
{
value.push_back(s[i] - '0');
}
increase(value);
return 0;
}
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
void find(vector<int> data)
{
int one, two;
int num1 = 0;
int num2 = 0;
vector<int>::iterator it;
for (it = data.begin(); it != data.end(); ++it)
{
if (num1 == 0)
{
one = *it;
num1 = 1;
}
else if (one == *it)
{
++num1;
}
else if (num2 == 0)
{
two = *it;
num2 = 1;
}
else if (two == *it)
{
++num2;
}
else
{
--num1;
--num2;
if (num1 == 0 && num2 != 0)
{
one = two;
num1 = num2;
num2 = 0;
}
}
}
if (num1 > 0)
{
num1 = 0;
for (it = data.begin(); it != data.end(); ++it)
{
if (*it == one)
{
++num1;
}
}
if (num1 > data.size() / 3)
{
cout << one << endl;
}
}
if (num2 > 0)
{
num2 = 0;
for (it = data.begin(); it != data.end(); ++it)
{
if (*it == two)
{
++num2;
}
}
if (num2 > data.size() / 3)
{
cout << two << endl;
}
}
}
int main()
{
int t;
vector<int> v;
/*while (scanf("%d", &t) != EOF)
{
v.push_back(t);
}*/
while (cin >> t)
{
v.push_back(t);
}
find(v);
return 0;
}
#include <iostream>
using namespace std;
void interleavings(string pre, string s1, int pos1, string s2, int pos2)
{
if (pos1 == s1.size())
{
cout << pre << s2.substr(pos2) << endl;
return;
}
if (pos2 == s2.size())
{
cout << pre << s1.substr(pos1) << endl;
return;
}
string pre1 = pre + s1.substr(pos1, 1);
string pre2 = pre + s2.substr(pos2, 1);
interleavings(pre1, s1, pos1 + 1, s2, pos2);
interleavings(pre2, s1, pos1, s2, pos2 + 1);
}
int main()
{
string s1, s2;
cin >> s1 >> s2;
interleavings("", s1, 0, s2, 0);
return 0;
}
#include <iostream>
#include <cstring>
using namespace std;
void merge(int *array, int *pos, int *result, int start, int mid, int end)
{
int temp[1000];
for (int i = start; i <= end; ++i)
{
temp[i] = pos[i];
}
int cur = start;
int leftcur = start;
int rightcur = mid + 1;
while (leftcur <= mid && rightcur <= end)
{
if (array[temp[leftcur]] <= array[temp[rightcur]])
{
pos[cur] = temp[leftcur];
result[pos[cur]] += rightcur - mid - 1;
++leftcur;
++cur;
}
else
{
pos[cur] = temp[rightcur];
++cur;
++rightcur;
}
}
while (leftcur <= mid)
{
pos[cur] = temp[leftcur];
result[pos[cur]] += end - mid;
++cur;
++leftcur;
}
while (rightcur <= end)
{
pos[cur] = temp[rightcur];
++cur;
++rightcur;
}
}
void mergesort(int *array, int *pos, int *result, int start, int end)
{
if (start >= end)
{
return;
}
int mid = start + (end - start) / 2;
mergesort(array, pos, result, start, mid);
mergesort(array, pos, result, mid + 1, end);
merge(array, pos, result, start, mid, end);
}
int main()
{
int array[1000];
int pos[1000];
int result[1000];
memset(result, 0, sizeof(int) * 1000);
int n;
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> array[i];
pos[i] = i;
}
mergesort(array, pos, result, 0, n - 1);
/*for (int i = 0; i < n; ++i)
{
cout << array[pos[i]] << " ";
}
cout << endl;*/
for (int i = 0; i < n; ++i)
{
cout << result[i] << " ";
}
cout << endl;
return 0;
}
using DP. When calculating the S[i], it may be got by three ways:
1. just input "A". So S[i] = S[i - 1] + 1
2. just "Ctrl-V", and the content in the buffer will be added to S[i - 1]
3. from i - 3, we will do "Ctrl-A" + "Ctrl-C" + "Ctrl-V", So the S[i] = S[i - 3] * 2, and the length of content in buffer will be S[i - 3].
Here is the code in C++;
#include <iostream>
using namespace std;
int maxlength(int n)
{
int s[1000];
int buff[1000];
s[0] = buff [0] = buff[1] = buff[2] = 0;
s[1] = 1;
s[2] = 2;
for (int i = 3; i <= n; ++i)
{
buff[i] = buff[i - 1];
s[i] = s[i - 1] + 1;
if (s[i - 1] + buff[i - 1] > s[i])
{
s[i] = s[i - 1] + buff[i - 1];
buff[i] = buff[i - 1];
}
if (s[i - 3] * 2 > s[i])
{
s[i] = s[i - 3] * 2;
buff[i] = s[i - 3];
}
cout << buff[i] << " " << s[i] << endl;
}
return s[n];
}
int main()
{
int n;
cin >> n;
int result = maxlength(n);
cout << result << endl;
return 0;
}
The first 10 result should be:
1:1
2:2
3:3
4:4
5:5
6:6
7:8
8:12
9:16
10:20
The result should be 10.
1. Create 7 * 7 matrix. Take race row by row. So it costs 7 races and every row is in increasing order.
2. Race the middle column, and sort the rows in the order of their middle column value. So the cars in the left and top of the center car of matrix should run slower than the center car. The cars in the right and bottom of the center car should run faster than the center car. They can not be the 25th car. Now we get
A[1][5],A[1][6],A[1][7]
A[2][5],A[2][6],A[2][7]
A[3][5],A[3][6],A[3][7]
A[4][3],A[4][4],A[4][5]
A[5][1],A[5][2],A[5][3]
A[6][1],A[6][2],A[6][3]
A[7][1],A[7][2],A[7][3]
and we want to find the 25th car in the 7*3 matrix.
3. Race the middle column, and sort the rows according to their middle value. Similar to the step 2, we can delete the cars which can't be the 25th car. And here remains a one-column matrix.
4. Race the remaining column and we get the middle car as the 25th car.
So the result should be 10 races.
#include <iostream>
using namespace std;
int num = 0;
bool graph[1000][1000];
int m;
int n;
int startx, starty, endx, endy;
void getpath(int x, int y, int path)
{
if (x - 1 >= 0 && !graph[x - 1][y])
{
graph[x - 1][y] = true;
getpath(x - 1, y, path - 1);
graph[x - 1][y] = false;
}
if (x + 1 < m && !graph[x + 1][y])
{
graph[x + 1][y] = true;
getpath(x + 1, y, path - 1);
graph[x + 1][y] = false;
}
if (y - 1 >= 0 && !graph[x][y - 1])
{
graph[x][y - 1] = true;
getpath(x, y - 1, path - 1);
graph[x][y - 1] = false;
}
if (y + 1 < n && !graph[x][y + 1])
{
graph[x][y + 1] = true;
getpath(x, y + 1, path - 1);
graph[x][y + 1] = false;
}
if (path == 0 && x == endx && y == endy)
{
++num;
}
}
int main()
{
cin >> m >> n;
int remain = m * n;
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
cin >> graph[i][j];
if (graph[i][j])
{
--remain;
}
}
}
cin >> startx >> starty >> endx >> endy;
--remain;
graph[startx][starty] = true;
getpath(startx, starty, remain);
cout << num << endl;
return 0;
}
This problem can be solved in O(n^2).
Basic DP:
Assume A[i] is the least cut number of string[1:i]. Then A[i + 1] should be min(A[i]+1, A[i-1]+check(i, i+1), A[i-2] + check(i-1,i+1), ....). Here check(i,j) do the check whether string[i:j] is palindromic, if it's false, (A[i - 1] + check(i, j)) should be unlimited large. It should cost O(n). So the time complexity of basic DP should be O(n^3).
However we can calculate check(i, j) in advance. Every time we choose an element (or two) as the center of palindrome, and spread towards left and right to get all the palindromes. So this preprocess cost O(n^2).
At last the DP can be solve in O(n^2) as check(i, j) can be calculated in O(1) after preprocess.
Here is the C++ code:
#include <iostream>
using namespace std;
int A[1000];
bool check[1000][1000];
int mincut(int *array, int n)
{
for (int i = 1; i <= n; ++i)
{
int offset = 0;
while (i - offset > 0 && i + offset <= n && array[i - offset] == array[i + offset])
{
check[i - offset][i + offset] = true;
++offset;
}
offset = 0;
while (i - offset > 0 && i + 1 + offset <= n && array[i - offset] == array[i + 1 + offset])
{
check[i - offset][i + 1 + offset] = true;
++offset;
}
}
A[0] = 0;
for (int i = 1; i <= n; ++i)
{
A[i] = A[i - 1] + 1;
for (int j = i - 1; j > 0; j -= 2)
{
if (check[j][i])
{
if (A[i] > A[j - 1] + 1)
{
A[i] = A[j - 1] + 1;
}
}
}
for (int j = i - 2; j > 0; j -= 2)
{
if (check[j][i])
{
if (A[i] > A[j - 1] + 1)
{
A[i] = A[j - 1] + 1;
}
}
}
}
return A[n];
}
int main()
{
int n;
int array[1000];
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> array[i];
}
int result = mincut(array, n);
cout << result << endl;
return 0;
}
Binary search the array, get the leftest element of k and the rightest element of k. Minus their positions.
Here is the c++ code:
#include <iostream>
using namespace std;
int left(int *array, int k, int start, int end)
{
if (start > end)
{
return -1;
}
while (start < end)
{
int mid = start + (end - start) / 2;
if (array[mid] == k)
{
end = mid;
}
else if (array[mid] > k)
{
end = mid - 1;
}
else
{
start = mid + 1;
}
}
if (array[start] == k)
{
return start;
}
return -1;
}
int right(int *array, int k, int start, int end)
{
if (start > end)
{
return -1;
}
if (start == end)
{
if (array[start] == k)
{
return start;
}
else
{
return -1;
}
}
while (start < end - 1)
{
int mid = start + (end - start) / 2;
if (array[mid] == k)
{
start = mid;
}
else if (array[mid] > k)
{
end = mid - 1;
}
else
{
start = mid + 1;
}
}
if (array[end] == k)
{
return end;
}
if (array[start] == k)
{
return start;
}
return -1;
}
int main()
{
int n, k;
int array[1000];
cin >> n >> k;
for (int i = 0; i < n; ++i)
{
cin >> array[i];
}
int l = left(array, k, 0, n - 1);
if (l == -1)
{
cout << "no such element" << endl;
return 0;
}
int r = right(array, k, 0, n - 1);
cout << r - l + 1 << endl;
return 0;
}
In the window, we should keep all the order of the elements. So the best way is using min heap to keep this order. And the time complexity would be O(nlog(k)).
Here is the c++ code:
#include <iostream>
#include <vector>
using namespace std;
class sliding{
private:
int heap[1000];
int id[1000];
int size;
int parent(int index)
{
return index / 2;
}
void insertheap(int *array, int index)
{
++size;
heap[size] = index;
id[index] = size;
top(array, size);
}
void swap(int i, int j)
{
id[heap[i]] = j;
id[heap[j]] = i;
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
void top(int *array, int index)
{
int p = parent(index);
if (array[heap[p]] > array[heap[index]])
{
swap(p, index);
top(array, p);
}
}
void deleteheap(int *array, int index)
{
int heapi = id[index];
swap(heapi, size);
--size;
down(array, heapi);
}
int left(int index)
{
return index * 2;
}
int right(int index)
{
return index * 2 + 1;
}
void down(int *array, int index)
{
int min = index;
int l = left(index);
int r = right(index);
if (l <= size && array[heap[l]] < array[heap[min]])
{
min = l;
}
if (r <= size && array[heap[r]] < array[heap[min]])
{
min = r;
}
if (min != index)
{
swap(min, index);
down(array, min);
}
}
public:
sliding():size(0)
{
size = 0;
heap[0] = -1;
}
vector<int> slidingWindow(int *array, int n, int k)
{
vector<int> result;
if (k == 1)
{
result.insert(result.begin(), array, array + n);
return result;
}
for (int i = 0; i < k; ++i)
{
insertheap(array, i);
}
result.push_back(array[heap[1]]);
for (int i = k; i < n; ++i)
{
int del = i - k;
deleteheap(array, del);
insertheap(array, i);
result.push_back(array[heap[1]]);
}
return result;
}
};
int main()
{
int n, k;
int array[1000];
sliding s;
cin >> n >> k;
for (int i = 0; i < n; ++i)
{
cin >> array[i];
}
vector<int> result = s.slidingWindow(array, n, k);
vector<int>::iterator iter;
for (iter = result.begin(); iter != result.end(); ++iter)
{
cout << *iter << " ";
}
cout << endl;
return 0;
}
Here is the c++ code.
#include <iostream>
using namespace std;
void swap(int *array, int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
int find(int *array, int n)
{
int i = 0;
int j = n - 1;
while (i <= j)
{
if (array[i] <= 0)
{
++i;
}
else
{
while (i <= j)
{
if (array[j] > 0)
{
--j;
}
else
{
swap(array, i, j);
++i;
--j;
break;
}
}
}
}
int positive = i;
while (i < n)
{
if (array[i] > n - positive)
{
++i;
}
if (array[i] == array[array[i] + positive - 1])
{
++i;
}
swap(array, i, array[i] + positive - 1);
}
for (int i = positive; i < n; ++i)
{
if (array[i] != i - positive + 1)
{
return i - positive + 1;
}
}
return n - positive + 1;
}
int main()
{
int n;
int array[1000];
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> array[i];
}
int result = find(array, n);
cout << result << endl;
return 0;
}
56 points are distributed to 8 team. In the worst case, team0 loses all the games, he gets 0 point. team1 win two games with team0 and loses all other games, he gets 2 points. In the same way, team2 gets 4 points, team3 gets 6 points. So there are 44 points left which can be distributed to the remaining 4 teams. So the assurance points for a team should be 11 points.
- wenlei.zhouwl May 22, 2012Traverse the array, every time remove two different elements. O(n).
So at last there will be two situations:
1. several elements are left and they have the same value. So this value is what we want. O(1)
2. two elements are left: one element which occurs n / 2, one other element. In this situation, we just need to traverse the array, and count the number occurs of the remaining element. O(n)
Here is the code:
#include <iostream>
using namespace std;
int find(int *array, int n)
{
int one = array[0];
int num = 1;
for (int i = 1; i + 1 < n; ++i)
{
if (num == 0)
{
one = array[i];
num = 1;
}
else
{
if (one == array[i])
{
++num;
}
else
{
--num;
}
}
}
if (num > 1)
{
return one;
}
else if (array[n - 1] == one)
{
return one;
}
else
{
int num = 0;
for (int i = 0; i < n; ++i)
{
if (array[i] == one)
{
++num;
}
}
if (num == n / 2)
{
return one;
}
else
{
return array[n - 1];
}
}
}
int main()
{
int n;
int array[1000];
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> array[i];
}
int result = find(array, n);
cout << result << endl;
return 0;
}
#include <iostream>
#include <cmath>
using namespace std;
int find(int *array, int n, int k)
{
for (int i = 0; i < n; )
{
int dis = abs(k - array[i]);
if (dis == 0)
{
return i;
}
i += dis;
}
return -1;
}
int main()
{
int n, k;
int array[1000];
cin >> n >> k;
for (int i = 0; i < n; ++i)
{
cin >> array[i];
}
int result = find(array, n, k);
cout << result << endl;
return 0;
}
for every person do BFS, get the cubicles which can be reached by every person. choose the least one.
- wenlei.zhouwl May 21, 20121. sort the input persons by height. O(nlogn)
2. find the longest increasing weight sequence in the sorted list. This can be done in O(nlogn) with DP.
given two number x, y. we should find the first digits from left to right which i.digit is different from y.digit.
here is the code.
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int i, int j)
{
int a[100];
int b[100];
int n1, n2;
if (i == 0)
{
a[0] = 0;
n1 = 1;
}
else
{
for (n1 = 0; i; ++n1)
{
a[n1] = i % 10;
i /= 10;
}
}
if (j == 0)
{
b[0] = 0;
n2 = 1;
}
else
{
for (n2 = 0; j; ++n2)
{
b[n2] = j % 10;
j /= 10;
}
}
for (--n1, --n2; n1 >= 0 && n2 >= 0; --n1, --n2)
{
if (a[n1] != b[n2])
{
break;
}
}
int s1, s2;
if (n1 >= 0 && n2 >= 0)
{
s1 = a[n1];
s2 = b[n2];
}
else if (n1 < 0 && n2 >= 0)
{
while (n2 >= 0)
{
if (a[0] == b[n2])
{
--n2;
}
else
{
break;
}
}
if (n2 >= 0)
{
s1 = a[0];
s2 = b[n2];
}
else
{
s1 = a[0];
s2 = b[0];
}
}
else if (n1 >= 0 && n2 < 0)
{
while (n1 >= 0)
{
if (a[n1] == b[0])
{
--n1;
}
else
{
break;
}
}
if (n1 >= 0)
{
s1 = a[n1];
s2 = b[0];
}
else
{
s1 = a[0];
s2 = b[0];
}
}
else
{
s1 = a[0];
s2 = b[0];
}
return s1 > s2;
}
void reorder(int *array, int n)
{
sort(array, array + n, cmp);
for (int i = 0; i < n; ++i)
{
cout << array[i];
}
cout << endl;
}
int main()
{
int n;
cin >> n;
int array[1000];
for (int i = 0; i < n; ++i)
{
cin >> array[i];
}
reorder(array, n);
return 0;
}
As we all know, we can modify the quick sort to find the k'th largest element in an array with the time complexity O(n). Now given two arrays, we can modify one array method to fit two arrays with some consideration about the index of an element. Here is the code.
#include <iostream>
using namespace std;
void swap(int* a1, int* a2, int n, int i, int j)
{
if (i < n)
{
int temp = a1[i];
if (j < n)
{
a1[i] = a1[j];
a1[j] = temp;
}
else
{
a1[i] = a2[j - n];
a2[j - n] = temp;
}
}
else
{
int temp = a2[i - n];
if (j < n)
{
a2[i - n] = a1[j];
a1[j] = temp;
}
else
{
a2[i - n] = a2[j - n];
a2[j - n] = temp;
}
}
}
int partition(int* a1, int* a2, int n, int start, int end)
{
int num;
if (end < n)
{
num = a1[end];
}
else
{
num = a2[end - n];
}
int i = start;
int j = end - 1;
while (i <= j)
{
int t;
if (i < n)
{
t = a1[i];
}
else
{
t = a2[i - n];
}
if (t <= num)
{
++i;
}
else
{
while (i <= j)
{
int tt;
if (j < n)
{
tt = a1[j];
}
else
{
tt = a2[j - n];
}
if (tt > num)
{
--j;
}
else
{
swap(a1, a2, n, i, j);
++i;
--j;
break;
}
}
}
}
swap(a1, a2, n, i, end);
return i;
}
int findk(int* a1, int* a2, int n, int k, int start, int end)
{
if (start == end)
{
if (start < n)
{
return a1[start];
}
else
{
return a2[start - n];
}
}
int p = partition(a1, a2, n, start, end);
if (p == k)
{
if (p < n)
{
return a1[p];
}
else
{
return a2[p - n];
}
}
else if (p > k)
{
return findk(a1, a2, n, k, start, p - 1);
}
else
{
return findk(a1, a2, n, k, p + 1, end);
}
}
int main()
{
int n, m, k;
int a1[1000];
int a2[1000];
cin >> n >> m >> k;
for (int i = 0; i < n; ++i)
{
cin >> a1[i];
}
for (int i = 0; i < m; ++i)
{
cin >> a2[i];
}
if (k < 1 || k > n + m)
{
cerr << "k is not valid" << endl;
return 0;
}
int result = findk(a1, a2, n, k - 1, 0, m + n - 1);
cout << result << endl;
return 0;
}
#include <iostream>
#include <algorithm>
#define MAX 1000
using namespace std;
struct cmp{
int index;
cmp():index(0){}
cmp(int i):index(i){}
bool operator()(int a[], int b[])
{
return a[index] < b[index];
}
};
void unique(int** array, int n)
{
for (int i = n - 1; i >= 0; --i)
{
cmp o(i);
sort(array, array + n, o);
}
int pre[1000];
for (int i = 0; i < n; ++i)
{
pre[i] = array[0][i];
cout << pre[i] << " ";
}
cout << endl;
for (int i = 1; i < n; ++i)
{
int j;
for (j = 0; j < n && pre[j] == array[i][j]; ++j)
{
}
if (j == n)
{
continue;
}
for (int j = 0; j < n; ++j)
{
cout << array[i][j] << " ";
pre[j] = array[i][j];
}
cout << endl;
}
}
int main()
{
int n;
cin >> n;
int **array = new int*[n];
for (int i = 0; i < n; ++i)
{
array[i] = new int[n];
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
cin >> array[i][j];
}
}
unique(array, n);
return 0;
}
This problem is some kind like such a question: find the largest path in a binary tree. So this problem can be solved from top to down.
#include <iostream>
#include <boost/unordered_map.hpp>
using namespace boost;
using namespace std;
struct Node{
int val;
Node* left;
Node* right;
};
unordered_map<Node*, int> l;
unordered_map<Node*, int> lh;
int max(int i, int j)
{
return i > j ? i : j;
}
int max(int i, int j, int k)
{
return max(max(i, j), k);
}
int largestheight(Node* T)
{
if (T == NULL)
{
return 0;
}
if (lh.find(T) != lh.end())
{
return lh[T];
}
int largest = max(largestheight(T->left), largestheight(T->right)) + T->val;
lh.insert(pair<Node*, int>(T, largest));
return largest;
}
int largest(Node* T)
{
if (T == NULL)
{
return 0;
}
if (l.find(T) != l.end())
{
return l[T];
}
int result = max(largest(T->left), largest(T->right), largestheight(T->left) + largestheight(T->right)) + T->val;
l.insert(pair<Node*, int>(T, result));
return result;
}
every time choose the center char; then expand to left and right.
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
vector<string> palindrome(char* array, int n)
{
vector<string> result;
for (int i = 1; i < n - 1; ++i)
{
int offset = 1;
while (i - offset >= 0 && i + offset < n && array[i - offset] == array[i + offset])
{
result.push_back(string(&array[i - offset], 1 + (offset << 1)));
++offset;
}
}
for (int i = 1; i < n - 1; ++i)
{
int offset = 0;
while (i - offset >= 0 && i + offset + 1 < n && array[i - offset] == array[i + offset + 1])
{
result.push_back(string(&array[i - offset], 2 + (offset << 1)));
++offset;
}
}
return result;
}
int main()
{
char array[1000];
cin >> array;
vector<string> result = palindrome(array, strlen(array));
vector<string>::iterator iter;
for (iter = result.begin(); iter != result.end(); ++iter)
{
cout << *iter << endl;
}
return 0;
}
#include <iostream>
#include <stack>
#include <climits>
#include <boost/unordered_map.hpp>
using namespace std;
using namespace boost;
template <typename T>
struct Node{
int freq;
T val;
};
template <typename T>
class freqstack{
private:
stack<T> s;
unordered_map<T, int> m;
Node<T>* heap[1000];
int heapsize;
int parent(int index)
{
return index / 2;
}
int leftchild(int index)
{
return index<<1;
}
int rightchild(int index)
{
return (index<<1) + 1;
}
void swap(int i, int j)
{
m[heap[i]->val] = j;
m[heap[j]->val] = i;
Node<T>* temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
void increase(int index)
{
int p = parent(index);
if (heap[p]->freq < heap[index]->freq)
{
swap(p, index);
increase(p);
}
}
void decrease(int index)
{
if (heap[index]->freq == 0)
{
swap(index, heapsize);
m.erase(heap[heapsize]->val);
delete heap[heapsize];
--heapsize;
}
int left = leftchild(index);
int right = rightchild(index);
int largest = index;
if (left <= heapsize && heap[left]->freq > heap[largest]->freq)
{
largest = left;
}
if (right <= heapsize && heap[right]->freq > heap[largest]->freq)
{
largest = right;
}
if (largest != index)
{
swap(largest, index);
decrease(largest);
}
}
public:
freqstack()
{
heap[0] = new Node<T>();
heap[0]->freq = INT_MAX;
heapsize = 0;
}
void push(T v)
{
if (m.find(v) == m.end())
{
if (heapsize == 999)
{
cerr << "no space" << endl;
return;
}
++heapsize;
m.insert(pair<T, int>(v, heapsize));
heap[heapsize] = new Node<T>();
heap[heapsize]->val = v;
heap[heapsize]->freq = 1;
}
else
{
int index = m[v];
heap[index]->freq++;
increase(index);
}
s.push(v);
}
void pop()
{
if (s.size() == 0)
{
cerr << "no element" << endl;
return;
}
int index = m[s.top()];
heap[index]->freq--;
decrease(index);
s.pop();
}
T top()
{
return s.top();
}
T max()
{
if (s.size() == 0)
{
cerr << "no element" << endl;
return -1;
}
return heap[1]->val;
}
~freqstack()
{
for (int i = 0; i <= heapsize; ++i)
{
delete heap[i];
}
}
};
int main()
{
freqstack<int> s;
s.push(1);
cout << s.max() << endl;
s.push(2);
s.push(2);
cout << s.max() << endl;
s.push(3);
s.push(3);
s.push(3);
cout << s.max() << endl;
s.push(2);
s.push(2);
cout << s.max() << endl;
s.pop();
s.pop();
cout << s.max() << endl;
s.push(7);
s.push(5);
s.push(9);
s.push(7);
s.push(9);
s.push(7);
s.push(7);
s.push(9);
s.push(7);
cout << s.max() << endl;
}
#include <iostream>
#include <cmath>
using namespace std;
long cache[1000];
long C(int k, int n)
{
long result = 1;
int index = 2;
for (int i = 0; i < k; ++i)
{
result *= n - i;
while (index <= k && result % index == 0)
{
result /= index;
++index;
}
}
return result;
}
long S(int n)
{
if (n == 0)
{
return 1;
}
if (n == 1)
{
return 1;
}
if (cache[n])
{
return cache[n];
}
int h = int(log(n) / log(2)) + 1;
int left, right;
if (n - (pow(2, h - 1) - 1) > pow(2, h - 2))
{
left = pow(2, h - 1) - 1;
}
else
{
left = n - pow(2, h - 2);
}
right = n - 1 - left;
long result = C(right, n - 1) * S(left) * S(right);
cache[n] = result;
return result;
}
int main()
{
int n;
cin >> n;
long result = S(n);
cout << result << endl;
return 0;
}
#include <iostream>
using namespace std;
double possibility[300][300][100];
int centerx = 100;
int centery = 100;
double calc(int n, int x, int y, int k)
{
int posx = x + centerx;
int posy = y + centery;
if (k == 0)
{
if (posx < centerx || posy < centery || posx >= centerx + n || posy >= centery + n)
{
return 0;
}
else
{
return 1;
}
}
if (possibility[posx][posy][k] != -1)
{
return possibility[posx][posy][k];
}
double result = 0;
result = 1.0 / 4 * (calc(n, x - 1, y, k - 1) + calc(n, x, y - 1, k - 1) + calc(n, x + 1, y, k - 1) + calc(n, x, y + 1, k - 1));
possibility[posx][posy][k] = result;
return result;
}
int main()
{
int n, x, y, k;
cin >> n >> x >> y >>k;
for (int i = 0; i < 300; ++i)
{
for (int j = 0; j < 300; ++j)
{
for (int g = 0; g < 100; ++g)
{
possibility[i][j][g] = -1;
}
}
}
double result = calc(n, x, y, k);
cout << result << endl;
return 0;
}
for a-b = c:
#include <iostream>
using namespace std;
void getTriple(int *array, int n)
{
for (int i = 0; i < n; ++i)
{
int sum = array[i];
int j = 0;
int k = n - 1;
while (j < k)
{
if (array[j] + array[k] < sum)
{
++j;
}
else if (array[j] + array[k] > sum)
{
--k;
}
else
{
if (i != j && i != k)
{
cout << sum << " " << array[j] << " " << array[k] << endl;
}
++j;
--k;
}
}
}
}
int main()
{
int n;
int array[1000];
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> array[i];
}
getTriple(array, n);
return 0;
}
for a+b+c=0
#include <iostream>
using namespace std;
void getTriple(int *array, int n)
{
for (int i = 0; i < n; ++i)
{
int sum = -1 * array[i];
int j = i + 1;
int k = n - 1;
while (j < k)
{
if (array[j] + array[k] < sum)
{
++j;
}
else if (array[j] + array[k] > sum)
{
--k;
}
else
{
cout << sum << " " << array[j] << " " << array[k] << endl;
++j;
--k;
}
}
}
}
int main()
{
int n;
int array[1000];
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> array[i];
}
getTriple(array, n);
return 0;
}
inorder + merge(merge in mergesort)
using namespace std;
struct Node{
int val;
Node* left;
Node* right;
};
void inorder(Node* T1, Node* T2)
{
Node* cursor1 = T1;
Node* cursor2 = T2;
bool done = false;
stack<Node*> s1;
stack<Node*> s2;
while (!done)
{
if (cursor1)
{
s1.push(cursor1);
cursor1 = cursor1->left;
}
else if (cursor2)
{
s2.push(cursor2);
cursor2 = cursor2->left;
}
else
{
if (!s1.empty() && !s2.empty())
{
if (s1.top()->val < s2.top()->val)
{
cursor1 = s1.top()->right;
s1.pop();
}
else if (s1.top()->val > s2.top()->val)
{
cursor2 = s2.top()->right;
s2.pop();
}
else
{
cout << s1.top()->val << endl;
cursor1 = s1.top()->right;
s1.pop();
cursor2 = s2.top()->right;
s2.pop();
}
}
else
{
done = true;
}
}
}
}
#include <iostream>
#include <cstdio>
#include <cassert>
using namespace std;
int v[1000][3];
int dp[1000][3];
int min(int a, int b)
{
if (a <= b)
{
return a;
}
return b;
}
int min(int a, int b, int c)
{
return min(min(a, b), c);
}
void printPath(int n)
{
int c = 0;
if (dp[n][1] < dp[n][c])
{
c = 1;
}
if (dp[n][2] < dp[n][c])
{
c = 2;
}
char buff[20];
sprintf(buff, "%d", c);
string result = string(buff);
for (int i = n - 1; i > 0; --i)
{
if (dp[i][(c + 1) % 3] <= dp[i][(c + 2) % 3])
{
c = (c + 1) % 3;
sprintf(buff, "%d", c);
result = string(buff) + " " + result;
}
else
{
c = (c + 2) % 3;
sprintf(buff, "%d", c);
result = string(buff) + " " + result;
}
}
cout << result << endl;
}
int paint(int n)
{
assert(n > 0);
dp[1][0] = v[1][0];
dp[1][1] = v[1][1];
dp[1][2] = v[1][2];
for (int i = 2; i <= n; ++i)
{
dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + v[i][0];
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + v[i][1];
dp[i][2] = min(dp[i - 1][1], dp[i - 1][0]) + v[i][2];
}
int result = min(dp[n][0], dp[n][1], dp[n][2]);
printPath(n);
return result;
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> v[i][0];
}
for (int i = 1; i <= n; ++i)
{
cin >> v[i][1];
}
for (int i = 1; i <= n; ++i)
{
cin >> v[i][2];
}
int result = paint(n);
cout << result << endl;
return 0;
}
#include <iostream>
#include <vector>
#include <set>
using namespace std;
vector<string> cache[1000];
int state[1000];
void split(const char* s, int start, int end, set<string> dic)
{
if (start > end)
{
return;
}
if (state[start])
{
return;
}
string ss;
vector<string> result;
for (int i = start; i <= end; ++i)
{
ss += s[i];
if (dic.find(ss) != dic.end())
{
split(s, i + 1, end, dic);
if (i == end)
{
result.push_back(ss);
}
else
{
vector<string>::iterator iter;
for (iter = cache[i + 1].begin(); iter != cache[i + 1].end(); ++iter)
{
result.push_back(ss + " " + *iter);
}
}
}
}
state[start] = 1;
cache[start] = result;
}
int main()
{
set<string> dic;
dic.insert("this");
dic.insert("is");
dic.insert("a");
dic.insert("awe");
dic.insert("we");
dic.insert("some");
dic.insert("awesome");
string s("thisisawesome");
split(s.c_str(), 0, s.length() - 1, dic);
vector<string>::iterator iter;
for (iter = cache[0].begin(); iter != cache[0].end(); ++iter)
{
cout << *iter << endl;
}
return 0;
}
this is right. inqueue will cost one push. dequeue will cost two pop and one push. So every operation still has time complexity of O(1).
- wenlei.zhouwl May 15, 2012
Repkaylafgioia, Cloud Support Associate at Absolute Softech Ltd
Hi, I am Kayla from Elkins USA. I am working as Project management and I have professional 3-year experience in ...
Repbrandysolsen, Area Sales Manager at AMD
I am a Social butterflies who enjoy travel.Have fun doing this job and project an atmosphere that reflects Amazon ...
use DP to calculate the square case. Time complexity should be O(n^2).
For rectangle case, DP is useless. So the time complexity should be O(n^4).
In the input, 0 means colored, 1means not colored.
Here is the c++ code.
- wenlei.zhouwl August 21, 2012