Algorithm ladder III
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;
}
}