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 這兩題都很有趣黎比。二分法求最優(yōu)
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
簡(jiǎn)單的求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
要點(diǎn)：最優(yōu)解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這類題差不多队丝，
* 這一類的題目都可以這樣做：
* 開(kāi)一個(gè)ResultType的變量result，
* 來(lái)儲(chǔ)存擁有最大average的那個(gè)node的信息。
* 然后用分治法來(lái)遍歷整棵樹(shù)傅事。
* 一個(gè)小弟找左子數(shù)的average茎辐，一個(gè)小弟找右子樹(shù)的average宪郊。
* 然后通過(guò)這兩個(gè)來(lái)計(jì)算當(dāng)前樹(shù)的average。
* 同時(shí)拖陆，我們根據(jù)算出來(lái)的當(dāng)前樹(shù)的average決定要不要更新result弛槐。
* 當(dāng)遍歷完整棵樹(shù)的時(shí)候，
* result里記錄的就是擁有最大average的子樹(shù)的信息依啰。/
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)
問(wèn)題是true or false乎串，按照divide and conquer，helper function也可以是true and false速警，另外需要傳遞的是depth這個(gè)量叹誉，所以naturally想到一個(gè)result type包含這兩個(gè)量鸯两。
比較smart的解法是把這兩個(gè)量合成一個(gè)量，false用-1表示长豁。（解法2）
package algorithm_ladder_III.normal_binary_tree;
/**
* leetcode 110
* 通過(guò)求深度來(lái)求判斷是否是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;
}
}
