biolxj12
BAN USER/*
* Find Kth largest element in given BST
* time: average case is O(logN), worst case is O(n) if it's not balanced BST
* space: O(1)
*
* idea:
n == num_elements(left subtree of tree), value=root.val;
n > num_elements(left subtree of T), ignore the left subtree, then find the k - num_elements(left subtree of T) smallest element of the right subtree.
n < num_elements(left subtree of T), find kth smallest element in left subtree.
*/
class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class findNLargestBST {
// assume it is balanced BST
public static int depth (TreeNode root) {
int depth =0;
if (root == null) return depth;
TreeNode tmp = root;
while (tmp !=null) {
tmp=tmp.left;
depth++;
}
return depth;
}
public static int NthElement (TreeNode root, int depth, int n) {
int count = (int) (Math.pow((double)2, depth) -1);
int e =0;
int index = count/2+1;
if (n == index) return e=root.val;
else if ( n< index) e = NthElement(root.left, depth-1, n);
else e= NthElement (root.right, depth-1, n-index);
return e;
}
public static int NthLargest (TreeNode root, int n) {
int depth = depth (root);
int count = (int) (Math.pow((double)2, depth) -1);
int e =0;
if (n > count) {
System.out.println("none");
e =0;
} else {
e = NthElement (root, depth, count-n+1);
}
return e;
}
public static void main (String[] args) {
/* find second largest:
* 20
* 10 30
* 40
*
*/
TreeNode n1 = new TreeNode(20);
TreeNode n2 = new TreeNode(10);
TreeNode n3 = new TreeNode(30);
TreeNode n4 = new TreeNode(40);
n1.left =n2; n2.right = n3;
n3.right = n4;
int n=2;
System.out.println(NthLargest(n1,n));
}
}
There are two things missing:
1. "The characters are case insensitive."
2. how about A - forum B - fourm, bulls - 3 cows - 2, but your code would be wrong.
public static void bullsAndCows(String p1, String p2){
if(p1 == null || p2 ==null)
throw new NullPointerException();
int[] p1Counts = new int[256];
int[] p2Counts = new int[256];
int n=p1.length();
int m=p2.length();
// find the bulls at the same location k
int k=0, bulls=0;
while (k<m && k<n) {
if (p1.toLowerCase().charAt(k) == p2.toLowerCase().charAt(k)) {
bulls++;
}
k++;
}
// store each char in array
for(int i=0; i < n; i++){
p1Counts[p1.toLowerCase().charAt(i)]++;
}
for(int j=0; j < m; j++){
p2Counts[p2.toLowerCase().charAt(j)]++;
}
int cows = 0;
for(int i = 0; i < 256; i++){
cows += Math.min(p1Counts[i], p2Counts[i]);
}
cows -= bulls;
System.out.println("Bulls = "+bulls+", Cows = "+cows);
}
public static void main (String[] args ) {
bullsAndCows("Picture","Epic");
bullsAndCows("forum","four");
}
correct me if I am wrong. Thx
- biolxj12 January 04, 2015public static boolean pal(String c){
c = c.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
int left=0, right=c.length()-1;
while (left<right){
if (c.charAt(left) != c.charAt(right)) return false;
else {left++;right--;}
}
return true;
}
public static void main(String[] args) {
String str = "A man, a plan, a canal: Panama";
System.out.println(pal(str));
}
Sorry, I did not get it.
If 2x2 sudoku, should be 8 possibilities.
If 4x4 sudoku, should be 288.
- biolxj12 February 23, 2015