braaap
BAN USERHere is my java implementation. If there are any optimizations that can be done, feel free to let me know. If all of the characters in the array are unique (no duplicates), then the function returns the first letter of the string (as all of the palindrome ranks are 1 in the string).
public class longestPalindromicSubstring {
public static String processString(String s){
// pads every character in the string with '#'
// example: string aba -> #a#b#a#, abba -> #a#b#b#a#
String t = new String("");
char[] s_c = s.toCharArray();
int left, right;
for (int i = 0; i < s_c.length; ++i){
t += "#" + s_c[i];
}
if (s_c[s_c.length-1] != '#')
t+= "#";
return t;
}
public static String longestPalindrome(String s){
String t = processString(s);
char[] t_array = t.toCharArray();
int max_size = t.length();
int[] memo = new int[max_size];
memo[0] = memo[max_size-1] = 0;
for (int i = 1; i < max_size-1;++i){
int offset = 1;
int count;
memo[i] = -1; // value will always be > -1 for the palindrome rank
if (t_array[i] == '#')
count = 0;
else
count = 1;
while (i + offset < max_size && i - offset > 0){
if (t_array[i+offset] != t_array[i-offset])
break;
if (t_array[i+offset] != '#')
count += 2;
// if they are part of the palindrome currently being viewed, they will have the same palindrome
// rank as their counterpart
memo[i+offset-1] = memo[i-offset+1];
++offset;
}
memo[i] = Math.max(count, memo[i]);
}
displayArrays(t_array, memo);
// find maximum palindrome rank
int max, center;
max = center = 0;
for (int j = 0; j < max_size; ++j){
if (memo[j] > max){
center = j;
max = memo[j];
}
}
//purely for debugging
//System.out.println("Max: " + max + " Center: " + center);
return s.substring((center-max)/2, (center+max)/2);
}
public static void displayArrays(char[] c, int[] v){
// function purely for the display of the arrays
// to easier understand what is going on with the algorithm
System.out.println("Character array: ");
System.out.print("{" + c[0]);
for (int i = 1; i < c.length;++i)
System.out.print(", " + c[i]);
System.out.println("}");
System.out.println("Palindrome value array: ");
System.out.print("{"+ v[0]);
for (int i = 1; i < v.length;++i)
System.out.print(", "+ v[i]);
System.out.println("}");
}
public static void main(String[] args) {
System.out.println(longestPalindrome("werqrewqaaaabbcbbaaaaadfafde"));
}
}
Here is my java solution. It is essentially the quick select algorithm used to find the kth largest number in an unsorted array. The algorithm assumes all elements in the array are unique (no duplicates). I also added the code to show the kth smallest element (commented out). I recommend not committing the code itself to memory, but rather working the algorithm out on paper until you understand the way the algorithm works.
public class findkthelement {
public static int selectKthLargest(int[] arr, int k) {
//ensure k is valid
if (k < 1 || k > arr.length){
return -1;
}
return findKthLargest(arr, 0, arr.length-1, k);
}
public static int findKthLargest(int[] nums, int start, int end, int k){
int pivot = start;
int left = start;
int right = end;
while (left <= right){
while (left <= right && nums[left] <= nums[pivot])
++left;
while (left<= right && nums[right]>= nums[pivot])
--right;
if (left < right){
swap(nums, left, right);
}
}
swap(nums, pivot, right);
/* code to find the kth largest element */
if (k == nums.length - right)
return nums[right];
else if (k > nums.length -right)
return findKthLargest(nums, start, right-1, k);
else
return findKthLargest(nums, right+1, end, k);
/****** code to find the kth smallest element --
* put here to show the slight difference between returning kth smallest
* and kth largest
if (k == right+1)
return nums[right];
else if (k > right+1)
return findKthLargest(nums, right+1, end, k);
else
return findKthLargest(nums, start, right-1, k);
*/
}
private static void swap(int[] nums, int a, int b){
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
public static void main(String[] args) {
int[] array = {2, -4, 5, 6, 0, 7, -1, 10, 9};
int k = 6;
System.out.print("{"+ array[0]);
for (int i = 1; i < array.length;++i)
System.out.print(", " + array[i]);
System.out.println("}");
System.out.println(k+"th largest element: " + selectKthLargest(array, k));
System.out.print("{"+ array[0]);
for (int i = 1; i < array.length;++i)
System.out.print(", " + array[i]);
System.out.println("}");
}
}
I had a little extra time, so here's the dynamic programming solution. Comments/criticisms are welcome.
public static int makeChangeDP(int[] denom, int sum){
if (sum == 0){
return 0;
} else {
int[] memo = new int[sum+1];
memo[0] = 0;
for (int j = 1; j < sum+1;++j)
memo[j] = Integer.MAX_VALUE -1;
for (int p = 1; p < sum+1;++p){
int min = Integer.MAX_VALUE-1;
for (int i = 0; i < denom.length;++i){
if (denom[i] <= p){
if (1+ memo[p-denom[i]]< min){
min = 1 + memo[p-denom[i]];
}
}
}
memo[p] = min;
}
return memo[sum];
}
}
Here is my recursive implementation in Java. I can post a dynamic programming version as well if needed. Comments, as always, are welcome.
public class minCoins {
public static int makeChange(int[] denom,int sum, int index) {
if (sum == 0){
return 0;
}
if (sum < 0 || index < 0) {
return Integer.MAX_VALUE-1;
}
return Math.min(makeChange(denom, sum-denom[index], index)+ 1,
makeChange(denom, sum, --index));
}
public static void main(String[] args) {
int[] coins = {1, 8, 11};
int sum = 24;
System.out.print("COINS: ");
for (int i = 0; i < coins.length;++i)
System.out.print(coins[i]+ " ");
System.out.println();
System.out.println("SUM: " + sum);
System.out.println("Minimum coins needed to reach sum of "
+ sum + " is: " + makeChange(coins, sum, coins.length-1) );
}
}
Yes, that is simpler, but the time complexity will be O(n^2).
- braaap July 02, 2013