poxzlm
BAN USERDP solution, the boundary is important.
#include <iostream>
using namespace std;
int num[50][50];
int main() {
string a = "decba", b = "cba", c = "deccbaba";
num[0][0] = 1;
for(int i = 0; i <= a.length(); i++) {
for(int j = 0; j <= b.length(); j++) {
if (i == 0 && j != 0 && b[j-1] == c[i+j-1]) {
num[i][j] = num[i][j-1];
} else if (i != 0 && j == 0 && a[i-1] == c[i+j-1]) {
num[i][j] = num[i-1][j];
}
if (i == 0 || j ==0) {
continue;
}
if(a[i-1] != b[j-1]) {
if(a[i-1] == c[i+j-1]) {
num[i][j] = num[i-1][j];
} else if (b[j-1] == c[i+j-1]) {
num[i][j] = num[i][j-1];
} else {
num[i][j] = 0;
}
} else {
if (a[i-1] == c[i+j-1]) {
num[i][j] = num[i][j-1] + num[i-1][j];
} else {
num[i][j] = 0;
}
}
}
}
cout << "Number of methods is " << num[a.length()][b.length()] << endl;
return 0;
}
This is a particular sorting problem. Type of element is string and the key issue is to define the "==", "<" and ">" operation. If string1 and string2 are anagrams, then string1"=="string2; else string1 "<" string2 or string1 ">"string2. Here's my solution:
1. Map the 26 letters to 26 prime numbers starting from 2, e.g. 2, 3, 5, 7,...
2. For a certain string a, compute map(a[0])*map(a[1])*map(a[2])*...*map(a[a.length()-1])
3. Assume string a gets _a and string b gets _b: if (_a==_b), then a==b; if(_a<_b), then a<b; if(_a>_b), then a>b
4. Depend on the compare operation, we just use Quick sort to sort the array.
Here's my solution, using matrix...
#include <iostream>
#define N 100
using namespace std;
int temp[N][N];
int main() {
int n = 3;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
temp[i][j] = i + 1 + j * n;
}
}
int count = 1;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << temp[i][j] << " ";
}
cout << endl;
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << temp[j][i] << " ";
}
cout << endl;
}
for(int i = 0; i < n; i++) {
cout << temp[i][i] << " ";
}
cout << endl;
for(int i = 0; i < n; i++) {
cout << temp[i][n-1-i] << " ";
}
cout << endl;
return 0;
}
Assume n,m<=32, my solution use bitmap:
Firstly we need to scan the the matrix and record down which rows and cols need to be set. Then for the second scanning we set the element according to the record done before.
int N, int M;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(a[i][j] == 1) {
N = N | (0x01 << i);
M = M | (0x01 << j);
}
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if((N & (0x01 << i)) || (M & (0x01 << j)))
a[i][j] = 1;
}
}
Firstly, we try to find the max distance by doing traversal. For each node Ni, max distance is max(1+heightOf(left(Ni))+heightOf(right(Ni))), and the exact Ni node (say M) with left sub-tree height value and right sub-tree height which gets max distance can be recorded. Then we do traversal again starting from M and find the two leaf nodes.
- poxzlm June 12, 2012Ok, actually I think it is a classic word participle problem which can be complex. Simply, we can use the Trie to store the dictionary. Then we scan the string to find the longest match words. Or we can build the Trie in reverse order of the words and scan the string in reverse order. U can search it with google :)
- poxzlm June 12, 2012
2 pivots patition:
- poxzlm July 01, 2012