综合题型

4. Median of Two Sorted Arrays

• 两个 Sorted Array
• 怎样做Binary Search?

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        m, n = len(nums1), len(nums2)
        if m > n:
            return self.findMedianSortedArrays(nums2, nums1)

        start, end = 0, m
        k = (m+n) // 2
        while start <= end:
            cut1 = start + (end - start) // 2
            cut2 = k - cut1
            l1 = nums1[cut1-1] if cut1 > 0 else -float('inf')
            l2 = nums2[cut2-1] if cut2 > 0 else -float('inf')
            r1 = nums1[cut1] if cut1 < m else float('inf')
            r2 = nums2[cut2] if cut2 < n else float('inf')
            if l1 > r2:
                end = cut1 - 1
            elif l2 > r1:
                start = cut1 + 1
            else:
                if (m+n) % 2:
                    return min(r1, r2)
                else:
                    return (max(l1,l2) + min(r1,r2)) / 2.0

29. Divide Two Integers

Division simply requires us to find how many times we can subtract the divisor from the the dividend without making the dividend negative

• 倍增法 1, 2, 4, 8, 16, 32, 64 ...

class Solution(object):
    def divide(self, dividend, divisor):
        # 先用异或处理符号
        np = (dividend < 0) ^ (divisor < 0)
        dividend = abs(dividend)
        divisor = abs(divisor)
        res = 0
        while dividend >= divisor:
            tmp, i = divisor, 1
            while dividend >= tmp:
                dividend -= tmp
                res += i
                i = i << 1
                tmp = tmp << 1
        if np:
            res = -res
        return min(max(-2147483648, res), 2147483647)

658. Find K Closest Elements

• 结合双指针

class Solution(object):
    def findClosestElements(self, arr, k, x):
        if x <= arr[0]:
            return arr[:k]
        elif x >= arr[-1]:
            return arr[-k:]
        else:
            index = bisect.bisect_left(arr, x)
            left = max(0, index-k)
            right = min(len(arr)-1, index+k-1)
            while right - left > k-1:
                if arr[right] - x >= x - arr[left]:
                    right -= 1
                else:
                    left += 1
            return arr[left:right+1]

300. Longest Increasing Subsequence

• 经典面试算法题“最长升序子序列“, 没做过的话, 很难想到O(nlogn)解法

class Solution(object):
    def lengthOfLIS(self, nums):
        if not nums: return 0

        n = len(nums)
        ends = [nums[0]]
        for i in xrange(1, n):
            if nums[i] > ends[-1]:
                ends.append(nums[i])
                continue

            start, end = 0, len(ends)-1
            while start < end:
                mid = start + (end - start) / 2
                if ends[mid] < nums[i]:
                    start = mid + 1
                else:
                    end = mid
            ends[start] = nums[i]
        return len(ends)