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

qoute

/*和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;
    }
}