gadolin
BAN USERGenerics were introduced to the Java language to provide tighter type checks at compile time and to support generic programming. To implement generics, the Java compiler applies type erasure to:
•Replace all type parameters in generic types with their bounds or Object if the type parameters are unbounded. The produced bytecode, therefore, contains only ordinary classes, interfaces, and methods.
•Insert type casts if necessary to preserve type safety.
•Generate bridge methods to preserve polymorphism in extended generic types.
Type erasure ensures that no new classes are created for parameterized types; consequently, generics incur no runtime overhead.
public class KNumSumToN {
public static int count(int k, int[] numbers, int n) {
return count(k, numbers, numbers.length-1, n);
}
public static int count(int k, int[] numbers, int index, int n) {
if (k == 0 && n == 0 || (k == 1 && index == 0 && n - numbers[0] == 0)) {
return 1;
} else if (index <= 0 || k < 0 || n < 0) {
return 0;
} else {
return count(k - 1, numbers, index - 1, n - numbers[index - 1])
+ count(k, numbers, index - 1, n);
}
}
public static void main(String[] args) {
int[] arr1= new int[] { 3,1,2,2,0,4,0};
System.out.println(count(2, new int[] { 1, 1, 0 }, 3));
System.out.println(count(2,arr1, 4));
}
}
package puzzles.twostacks;
public class TreeArrayHeight {
int getAndSetHeight(int[] array, int index) {
if (array[index] == -1) {
return 1;
}
if (array[index] >= 0) {
array[index] = -(getAndSetHeight(array, array[index]) + 1);
}
return -array[index];
}
public void getMaxHeight(int[] array) {
for (int i = 0; i < array.length; i++) {
getAndSetHeight(array, i);
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < array.length; i++) {
min = Math.min(min, array[i]);
}
System.out.println(-min-1);
}
public static void main(String[] args) {
new TreeArrayHeight().getMaxHeight(new int[]{-1,0,1,2,3,4});
}
}
This will print all pairs (based on their indexes), even if we have repeating numbers , e.g.
[1,2,2,3],4
will print (1,3), (2,2).
[1,2,2,2,3],4
will print
(1,3),(2,2),(2,2),(2,2)
import java.util.HashMap;
import java.util.Map;
public class PairSum {
public void printPairs(int[] arr, int target) {
Map<Integer, Integer> elementCount = new HashMap<Integer, Integer>();
for (int el : arr) {
increaseElementCount(el,elementCount);
}
for (int el : arr) {
Integer count = elementCount.get(target - el);
if (count != null && count > 0) {
int matchingPairs = count;
if (isHalf(el, target)) {
matchingPairs--;
}
for (int i = 0; i < matchingPairs; i++) {
System.out.println("(" + el + "," + (target - el)+")");
}
int numberOfEl = elementCount.get(el);
elementCount.put(el, --numberOfEl);
}
}
}
private void increaseElementCount(int el, Map<Integer,Integer> map) {
Integer count = map.get(el);
if (count == null) {
count = 0;
}
map.put(el, ++count);
}
private boolean isHalf(int el, int target) {
return (target == 2 * el);
}
public static void main(String[] args) {
new PairSum().printPairs(new int[]{0,1,2,2,3,4}, 4);
}
}
I think none of them is valid AVL, as they dont preserve the constraint that all left children should be less/equal then the parent and and right children should be greater/equal, so we should see in the same time left and right children less then root, so:
- gadolin July 29, 2012a) 5 is on the left and 2 is on the right
b) L:2, R:5
c)L:6, R:5
d) all right children, so its 0 height on the left and at least 2 on the right