2/3 二分答案 binary search的应用

median of two sorted array

对于找中位数问题，等价于find kth largest elements, 奇数元素找一遍，偶数元素找两遍。

the basic idea is that 每次可以扔掉A或B里面，较小的那k / 2个数，使得A与B的剩余搜索范围单调向右，而k指数缩小。

time: O(log(k)) where k is (m + n) / 2

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;

        if (len % 2 == 1) {
            return findKth(nums1, 0, nums2, 0, len / 2 + 1);
        } else {
            return (findKth(nums1, 0, nums2, 0, len / 2) + 
                    findKth(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;
        }
    }

    private int findKth(int[] A, int startA, int[] B, int startB, int k) {
        // base case 
        if (startA == A.length) return B[startB + k - 1];
        if (startB == B.length) return A[startA + k - 1];
        if (k == 1) return Math.min(A[startA], B[startB]);

        // recursive case
        int keyA = (startA + k / 2 - 1 < A.length)
                   ? A[startA + k / 2 - 1]
                   : Integer.MAX_VALUE;
        int keyB = (startB + k / 2 - 1 < B.length)
                   ? B[startB + k / 2 - 1]
                   : Integer.MAX_VALUE;
        if (keyA < keyB) {
            return findKth(A, startA + k/2, B, startB, k - k/2);
        } else {
            return findKth(A, startA, B, startB + k/2, k - k/2);
        }
    }
}

note:

• 当array A 或 B剩下的元素不够k/2个，注意要设key 为 Integer.MAX_VALUE, 这样让对方array去除k/2元素。
• 在做DFS，表明接下来要去找第几大的元素，需要做减法 k - k/2。因为有可能k是奇数，会有decimal division with rounding.

count complete tree node

the idea is straightforward if we can draw the graph, but the runtime complexity is a little tricky:

based on master theorem, the runtime of an algorithm can be expressed by the recurrence relation:

: T(n) = a T(n/b) + f(n) where a = 1, b = 2, f(n) = log(n)

so C(crit) = log b (a) = 0; so it satisfy the second cases, and we can conclude that T(n) = Theta(log(n) ^ 2).

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;

        int left = getHeight(root.left);
        int right = getHeight(root.right);
        if (left == right) {
            return countNodes(root.right) + (1 << left);
        } else {
            return countNodes(root.left) + (1 << right);
        }
    }

    private int getHeight(TreeNode node) {
        int height = 0;
        while (node != null) {
            height++;
            node = node.left;
        }
        return height;
    }
}

Russian Doll Envelopes

one straightforward idea is that 我们可以先对weight进行排序，然后在height上做LIS。

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0) return 0;

        int n = envelopes.length;
        int m = envelopes[0].length;

        // sort the original integer array based on the weight
        Arrays.sort(envelopes, (int[] a, int[] b) -> a[0] - b[0]);

        // do the LIS based on the height
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i = 1; i < envelopes.length; ++i) {
            for (int j = 0; j < i; ++j) {
                if (envelopes[i][1] > envelopes[j][1] &&
                    envelopes[i][0] > envelopes[j][0]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

need to complete:

Max Sum of Rectangle No Larger Than K

Split Array Largest Sum

Is Subsequence

Maximum Length of Repeated Subarray

Heaters