pws
BAN USERResizing the array is required iff. each digit in the input is a 9. We perform one linear pass to determine if this is the case, and if so we allocate an array of size n+1 and fill in values {1, 0, 0, ...}. Otherwise, we start from the rightmost digit and set all A[i] to 0 until we reach a digit that's not 9, which we increment.
- pws July 12, 2012char* interleaveStrings(char* str1, char* str2, char[] result, int i) {
if (*str1 == '\0' and *str2 == '\0') {
printf(result);
}
else if (*str1 == '/0') {
result[i] = *str2;
interleaveStrings(str1, str2++, result, i+1);
}
else if (*str2 == '/0') {
result[i] = *str1;
interleaveStrings(str1++, str2, result, i+1);
}
else {
result[i] = *str2;
interleaveStrings(str1, str2++, result, i+1);
result[i] = *str1;
interleaveStrings(str1++, str2, result, i+1);
}
}
void main() {
char* str1 = "asdf";
char* str2 = "qwerty";
char result[10];
interleaveStrings(str1, str2, result, 0);
}
Use a stack. Perform one linear pass through the string, compare current element to the one on top of the stack. If they're the same, pop the element and increment the counter. If not, clear the contents of the stack and push current element onto stack.
EDIT: sorry this is wrong.
This generates all the permutations of the input string. I think the key observation is that an anagram is a permutation of the characters in a string that's also a WORD. So what we would need in this situation is a dictionary which tell us whether or not a given permutation is an English word. All n! permutations would have to be examined anyway...that's the lower bound AFAIK.
- pws July 08, 2012public static int equilibrium(int[] data){
int partial_sums = int[data.length];
partial_sums[0] = data[0];
for (int i = 1; i < data.length; i++) {
partial_sums[i] = partial_sums[i - 1] + data[i];
}
for (int i = 1; i < data.length; i++) {
if (partial_sums[i] == partial_sums[data.length - 1] - partial_sums[i]) {
return i;
}
}
}
use a C/C++ function pointer?
- pws August 02, 2012