Dec 27, 28
Binary Search
lintcode 61 search-for-a-range
lintcode 38 Search a 2D Matrix II, leetcode 240
lintcode 160.Find Minimum in Rotated Sorted Array II
lintcode 63.Search in Rotated Sorted Array II
leetcode 69. Sqrt(x), square root of an integer
lintcode 586 Sqrt(x) II, square root of a double
lintcode 160.Find Minimum in Rotated Sorted Array II --- TO DO
lintcode 63.Search in Rotated Sorted Array II ---- TO DO
lintcode 617.Maximum Average Subarray --- TO DO
lintcode 437.Copy Books --- TO DO
lintcode 183.Wood Cut -- TO DO 这两题都很有趣。二分法求最优
Binary tree, Divide and Conquer
lintcode 597.Subtree with Maximum Average
lintcode 110 Balanced Binary Tree (easy but typical)
lintcode 61 search-for-a-range
简单的求first 求last
package algorithm_ladder_III;
/**
* lintcode 61
*
*/
public class SearchForARange {
public int[] searchRange(int[] A, int target) {
// corner case:
if (A==null || A.length == 0) {
return new int[] {-1, -1};
}
int first = findBoundary(A, target, true);
if (first == -1) return new int[] {-1, -1};
int last = findBoundary(A, target, false);
return new int[] {first, last};
}
// findFirst = true: find first of target
// else find last of target;
private int findBoundary(int[] A, int target, boolean findFirst) {
int lo = 0, hi = A.length -1;
while (lo + 1 < hi) {
int mid = lo + (hi-lo) / 2;
if ( target > A[mid]) {
lo = mid;
} else if (target < A[mid]) {
hi = mid;
} else {
if (findFirst) {
hi = mid;
} else {
lo = mid;
}
}
}
if (findFirst) {
if (A[lo] == target) return lo;
else if (A[hi] == target) return hi;
else return -1;
} else {
if (A[hi] == target) return hi;
else if (A[lo] == target) return lo;
else return -1;
}
}
public static void main(String[] args) {
int[] A = new int[] {5, 7, 7, 8, 8, 10};
int target = 8;
SearchForARange s = new SearchForARange();
int[] res = s.searchRange(A, target);
System.out.println(res[0] + " " + res[1]); // should be [3, 4]
}
}
lintcode 38 Search a 2D Matrix II
search a 2D matrix II
要点：最优解O(m+n) 走anti-diagonal entries.
一般解得化，可以逐行搜索；
package algorithm_ladder_III;
/**
* leetcode 240
*/
public class SearchA2DMatrixII {
public int searchMatrix(int[][] A, int target) {
// corner case
if (A == null || A.length == 0)
return 0;
int i = A.length-1, j = 0; // i^th row, j^th col --- the bottom left corner of the matrix
int result = 0;
while (i >= 0 && j < A[0].length) {
if (A[i][j] > target) {
i--;
} else if (A[i][j] < target) {
j++;
} else {
result++;
i--;
j++;
}
}
return result;
}
public static void main(String[] args) {
int[][] A = new int[3][4];
A[0] = new int[] {1, 3, 5, 7};
A[1] = new int[] {2, 4, 7, 8};
A[2] = new int[] {3, 5, 9, 10};
int target = 3;
SearchA2DMatrixII s = new SearchA2DMatrixII();
System.out.println(s.searchMatrix(A, target)); // should be 2
}
}
leetcode 69. Sqrt(x)
package algorithm_ladder_III;
public class Sqrt {
public int mySqrt(int x) {
// corner case;
if (x == 0) return 0;
int lo = 1, hi = x;
while (lo + 1 < hi) {
int mid = lo + (hi - lo) / 2;
if (mid * mid < x) lo = mid;
else if (mid * mid > x) hi = mid;
else return mid;
}
System.out.println(lo + " " + hi);
if (hi * hi <= x) return hi;
else return lo;
}
public static void main(String[] args) {
int x = 8;
Sqrt s = new Sqrt();
System.out.println(s.mySqrt(x)); // should be 2
}
}
lintcode 586 Sqrt(x) II
package algorithm_ladder_III;
public class SqrtII {
public double sqrt(double x) {
double lo = 0.0, hi;
if (x > 1) hi = x;
else hi = 1;
while (lo + 1e-12 < hi) {
double mid = lo + (hi-lo) / 2;
if (x < mid * mid) hi = mid;
else if (x > mid * mid) lo = mid;
else return mid;
}
return lo;
}
public static void main(String[] args) {
double x = 2;
SqrtII s = new SqrtII();
System.out.println(s.sqrt(x)); // should be 1.41421356
}
}
lintcode 597.Subtree with Maximum Average
/*和path，Minimum Subtree这类题差不多，
* 这一类的题目都可以这样做：
* 开一个ResultType的变量result，
* 来储存拥有最大average的那个node的信息。
* 然后用分治法来遍历整棵树。
* 一个小弟找左子数的average，一个小弟找右子树的average。
* 然后通过这两个来计算当前树的average。
* 同时，我们根据算出来的当前树的average决定要不要更新result。
* 当遍历完整棵树的时候，
* result里记录的就是拥有最大average的子树的信息。/
package algorithm_ladder_III.subtree_with_maximum_average;
public class SubtreeWithMaxAverage {
class ResultType {
int count;
int sum;
public ResultType(int count, int sum) {
this.count = count;
this.sum = sum;
}
}
private TreeNode ResultNode = null;
private double MaxAvg = Double.MIN_VALUE;
public TreeNode findSubtree(TreeNode root) {
sumAndCount(root);
return ResultNode;
}
private ResultType sumAndCount(TreeNode root) {
if (root == null) {
return new ResultType(0, 0);
}
ResultType left = sumAndCount(root.left);
ResultType right = sumAndCount(root.right);
int newSum = left.sum + right.sum + root.val;
int newCount = left.count + right.count + 1;
ResultType r = new ResultType(newCount, newSum);
if (MaxAvg < ((double) newSum / (double) newCount)) {
MaxAvg = ((double) newSum / (double) newCount);
ResultNode = root;
}
return r;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(3);
TreeNode left = new TreeNode(1); left.left = new TreeNode(10); left.right = new TreeNode(15);
TreeNode right = new TreeNode(2); right.left = new TreeNode(4); right.right = new TreeNode(5);
root.left = left; root.right = right;
SubtreeWithMaxAverage s = new SubtreeWithMaxAverage();
TreeNode node = s.findSubtree(root);
System.out.println(node.val); // should be 1;
}
}
lintcode 110 Balanced Binary Tree (easy but typical)
问题是true or false，按照divide and conquer，helper function也可以是true and false，另外需要传递的是depth这个量，所以naturally想到一个result type包含这两个量。
比较smart的解法是把这两个量合成一个量，false用-1表示。（解法2）
package algorithm_ladder_III.normal_binary_tree;
/**
* leetcode 110
* 通过求深度来求判断是否是balanced
*/
public class BalancedBinaryTree {
class ResultType {
int depth;
boolean isBalanced;
ResultType(int depth, boolean isBalanced) {
this.depth = depth;
this.isBalanced = isBalanced;
}
}
public boolean isBalanced(TreeNode root) {
ResultType res = checkHeightAndBalance(root);
return res.isBalanced;
}
private ResultType checkHeightAndBalance(TreeNode root) {
if (root == null) return new ResultType(0, true);
ResultType left = checkHeightAndBalance(root.left);
ResultType right = checkHeightAndBalance(root.right);
int newDepth = 1+ Math.max(left.depth, right.depth);
boolean newIsBalanced = left.isBalanced && right.isBalanced && Math.abs(left.depth - right.depth) <= 1;
return new ResultType(newDepth, newIsBalanced);
}
}
or
package algorithm_ladder_III.normal_binary_tree;
/**
* Alternative solution to leetcode 110
*/
public class BalancedBinaryTreeII {
public boolean isBalanced(TreeNode root) {
int r = getHeight(root);
return r != -1;
}
public int getHeight(TreeNode root) {
if (root == null) return 0;
int left = getHeight(root.left);
int right = getHeight(root.right);
if (left == -1 || right == -1) return -1;
if (Math.abs(left - right) <= 1) return 1 + Math.max(left, right);
return -1;
}
}
