roberto.triviani
BAN USERMost of you are not checking error conditions.
Try it with a list of length 1. Some of the above solutions I've seen will actually return null for the new head.
static DoublyLinkedNode reverse(DoublyLinkedNode head) {
while (head.next != null) {
DoublyLinkedNode tmpNext = head.prev;
head.prev = head.next;
head.next = tmpNext;
head = head.prev;
}
head.next = head.prev;
head.prev = null;
return head;
}
int sum = 5;
List<Integer> input = Arrays.asList(2,3,4,9,-1,9,12);
List<Integer> current = Arrays.asList();
List<List<Integer>> results = new ArrayList<List<Integer>>();
getCombinationsThatSumTo(sum, input, current, results);
static void getCombinationsThatSumTo(int desiredSum, List<Integer> input, List<Integer> current, List<List<Integer>> results)
{
if (input.isEmpty()) return;
int sum = 0;
for (int i = 0; i < current.size(); i++) {
sum += current.get(i);
}
if (sum == desiredSum) {
results.add(current);
//for ease, just print it.
for (int j = 0; j < current.size(); j++) {
System.out.print(current.get(j)+",");
}
System.out.println("");
}
getCombinationsThatSumTo(desiredSum, input.subList(1, input.size()), current, results);
List<Integer> newCurrent = new ArrayList<Integer>(current);
newCurrent.add(input.get(0));
getCombinationsThatSumTo(desiredSum, input.subList(1, input.size()), newCurrent, results);
}
The approach by Erasmus will not work due to running out of memory. MD5 hash size is 15 bytes so you will need 15 Gbytes to store hashes for sentences in the first file.
As the author above states, you perform an external sort in o(nlogn), and then do a comparison which is o(n).
Complexity: O(N^2)
Explanation: Look for odd length palindromes centered at i, look at even length palindromes starting with i as the left character.
Note: not sure why formatting is off.
//O(N^2) implementation
int numPallindromes3(String s) {
int numPallindromesCounter = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = 1; j < s.length()/2; j++) {
if (i - j < 0 || i + j >= s.length()) continue;
String odd1 = s.substring(i-j, i-j+1);
String odd2 = s.substring(i+j, i+j+1);
if (odd1.equals(odd2)) {
numPallindromesCounter++;
System.out.println(s.substring(i-j,i+j+1));
} else
break;
}
for (int k = 1; k < s.length()/2 + 1; k++) {
if (i - k + 1< 0 || i + k >= s.length()) continue;
String even1 = s.substring(i-k+1, i-k+2);
String even2 = s.substring(i+k, i+k+1);
if (even1.equals(even2)) {
numPallindromesCounter++;
System.out.println(s.substring(i-k+1,i+k+1));
} else
break;
}
}
return numPallindromesCounter;
}
- roberto.triviani November 08, 2013