denys.o.p
BAN USERHere is my solution insensitive to char case with test cases:
public class PalindromInplaceCheck {
private static boolean isPalindrome(String text){
int length = text.length();
for(int i = 0; i < length; i++)
if(Character.toLowerCase(text.charAt(i)) != Character.toLowerCase(text.charAt(length - i - 1)))
return false;
return true;
}
public static void main(String [] args){
String testString1 = new String("common");
System.out.println(testString1 + " is a palindrom: " + isPalindrome(testString1));
String testString2 = new String("palIndromoRdniLap");
System.out.println(testString2 + " is a palindrom: " + isPalindrome(testString2));
String testString3 = new String("a");
System.out.println(testString3 + " is a palindrom: " + isPalindrome(testString3));
String testString4 = new String("");
System.out.println(testString4 + " is a palindrom: " + isPalindrome(testString4));
String testString5 = new String("abBa");
System.out.println(testString5 + " is a palindrom: " + isPalindrome(testString5));
String testString6 = new String("cdc");
System.out.println(testString6 + " is a palindrom: " + isPalindrome(testString6));
}
}
InOrder traversal solution without recursion.
public class problem_7{
public static class Node{
public Node left;
public Node right;
public Integer value;
public Node(Integer v){
value = v;
}
}
public static int find(Node head, int k){
Stack<Node> stack = new Stack<Node>();
HashMap<Node, Boolean> used = new HashMap<Node, Boolean>();
stack.push(head);
int count = 0;
while(!stack.empty()){
Node currentNode = stack.pop();
if(currentNode == null) continue;
if(currentNode.left == null || used.containsKey(currentNode.left) == true){
used.put(currentNode, true);
count++;
if(count == k)
return currentNode.value;
continue;
}
stack.push(currentNode.right);
stack.push(currentNode);
stack.push(currentNode.left);
}
return -Integer.MAX_VALUE;
}
public static void main(String [] args){
Node head = new Node(4);
Node l_1 = new Node(5);
Node r_1 = new Node(0);
Node l_21 = new Node(3);
Node l_22 = new Node(7);
l_1.left = l_21;
l_1.right = l_22;
head.left = l_1;
head.right = r_1;
System.out.println(problem_7.find(head, 5));
}
}
Here is my solution. Time complexity O(logn).
public class FIndLocalMinimum{
public int localMinimum(int [] arr, int left, int right){
if(left == right) return left;
if(right - left == 1) {
if(arr[left] < arr[right])
return left;
else
return right;
}
int mid = left + (right - left) / 2;
int result = -1;
if(arr[mid - 1] > arr[mid] && arr[mid + 1] > arr[mid])
result = mid;
else{
if(arr[mid - 1] < arr[mid])
result = localMinimum(arr, left, mid - 1);
else if(arr[mid + 1] < arr[mid])
result = localMinimum(arr, mid + 1, right);
}
return result;
}
public static void main(String [] args){
FIndLocalMinimum c = new FIndLocalMinimum();
int [] test = new int[7];
test[0] = 11;
test[1] = 5;
test[2] = 12;
test[3] = 7;
test[4] = 4;
test[5] = 0;
test[6] = 6;
System.out.println(c.localMinimum(test, 0, test.length - 1));
}
}
Greedy solution with memoization.
(Here I omit test if N is out of memo array bounds)
public class problem_5 {
private int[] _memo;
public int getK(int N){
double n = (double)N;
int result = 0;
while(n != 0.0){
if(_memo[(int)n] != 0){
result += _memo[(int)n];
break;
} else {
double maxLessSquare = Math.floor(Math.sqrt(n));
n = n - (maxLessSquare * maxLessSquare);
result += 1;
}
}
_memo[N] = result;
return result;
}
public problem_5(){
int memoSize = 1000;
_memo = new int[memoSize];
for(int i = 0; i < memoSize; i++)
_memo[i] = 0;
}
public static void main(String [] args){
problem_5 p = new problem_5();
System.out.println(p.getK(15));
System.out.println(p.getK(9));
System.out.println(p.getK(8));
}
}
Here is my solution:
1) Sort the array according to the values of pointers.
2) Scan the array and when the [next element] not equals to [previos + 1] increment the result.
Time complexity O(nlogn), memory complexity O(logn) - sorting recursion stack size.
public static class Node{
public Node left;
public Node right;
public Integer value;
public Node(int v){
value = v;
}
}
private void exch(Node [] arr, int p, int q){
Node t = arr[p];
arr[p] = arr[q];
arr[q] = t;
}
private int partition(Node [] arr, int left, int right){
if(left > right) return -1;
int pivot = left;
int thresh = pivot;
for(int i = left + 1; i <= right; i++){
if(arr[pivot].value > arr[i].value)
exch(arr, ++thresh, i);
}
exch(arr, thresh, pivot);
return thresh;
}
private void quickSort(Node [] arr, int left, int right){
int pivot = partition(arr, left, right);
if(pivot < 0) return;
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
public int getResult(Node [] arr){
quickSort(arr, 0, arr.length - 1);
int result = 1;
for(int i = 0; i < arr.length - 1; i++){
if(arr[i].value + 1 != arr[i + 1].value)
result += 1;
}
return result;
}
public static void main(String [] args){
Node [] arr = new Node[7];
problem_4 d = new problem_4();
arr[0] = new Node(9);
arr[1] = new Node(1);
arr[2] = new Node(3);
arr[3] = new Node(7);
arr[4] = new Node(8);
arr[5] = new Node(5);
arr[6] = new Node(2);
System.out.println(d.getResult(arr));
}
In worst case your solution takes O(nlogn) time not O(logn*logn). Suppose that your else
else {
// root is not one of the numbers, try it's both subtrees
bstTwoSum(root.left, target);
bstTwoSum(root.right, target);
}
happens each time. Thus you will travers all over the tree that has n nodes.
- denys.o.p January 27, 2015I wrote the next solution in google doc. It uses binary serach so the time complexity is O(m * lg n)
public class Main{
private int leftmostBinSearch(int [] arr, int v, int l, int r){
if(l > r) return -1;
int mid = l + (r - l) / 2;
if(arr[mid] == v){
int leftmost = leftmostBinSearch(arr, v, l, mid - 1);
if(leftmost > -1)
return leftmost;
return mid;
}
if(arr[mid] < v)
leftmostBinSearch(arr, v, mid + 1, r);
if(arr[mid] > v)
leftmostBinSearch(arr, v, l, mid - 1);
return -1;
}
public int findRow(int [][] arr){
if(arr == NULL) return -1;
int rows = arr[0].length;
int maxIndex = -1;
int maxQuantity = -1;
for(int i = 0; i < rows; i++){
int currentQuantity = leftmostBinSearch(arr[i], 1);
if(currentQuantity > maxQuantity){
maxQuantity = currentQuantity;
maxIndex = i;
}
}
return maxIndex;
}
}
- denys.o.p May 14, 2015