Sorting and Searching

1 First Bad Version

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        if not n:
            return -1

        l, r = 0, n + 1
        while l<r:
            mid = (l+r)//2
            if isBadVersion(mid):
                r = mid
            else:
                l = mid + 1
        return l

2 Meeting Rooms II

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        times = []
        for interval in intervals:
            times.append((interval.start, 1))
            times.append((interval.end, 0))

        times.sort()
        cnt = 0
        res = 0
        for i in range(len(times)):
            if times[i][1]:
                cnt += 1
                res = max(res, cnt)
            else:
                cnt -= 1
        return res

3 Merge Sorted Array

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        while m > 0 and n > 0:
            if nums1[m-1] > nums2[n-1]:
                nums1[m+n-1] = nums1[m-1]
                m -= 1
            else:
                nums1[m+n-1] = nums2[n-1]
                n -= 1
        if n:
            nums1[:n] = nums2[:n]

4 Merge Two Sorted Lists

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        head = dummy

        while l1 and l2:
            if l1.val < l2.val:
                dummy.next = l1
                l1 = l1.next
            else:
                dummy.next = l2
                l2 = l2.next
            dummy = dummy.next

        if l1 or l2:
            dummy.next = l1 or l2
        return head.next

5 Merge k Sorted Lists

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        heap = []
        dummy = ListNode(-1)
        cur = dummy

        for node in lists:
            if node:
                heapq.heappush(heap, [node.val, node])

        while heap:
            node = heapq.heappop(heap)[1]
            cur.next = node
            cur = cur.next
            if node.next:
                heapq.heappush(heap, [node.next.val, node.next])

        return dummy.next

6 Search in Rotated Sorted Array

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums: return -1
        l, r = 0, len(nums)

        while l < r:
            mid = (l + r)//2
            if nums[mid]  == target:
                return mid

            if nums[l] < nums[mid]: # left in order
                if nums[l] <= target < nums[mid]:
                    r = mid
                else:
                    l = mid + 1
            else: # right in order
                if nums[mid] < target <= nums[-1]:
                    l = mid + 1
                else:
                    r = mid
        return -1

7 Search in Rotated Sorted Array II

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        if not nums: return False
        l, r = 0, len(nums)

        while l < r:
            mid = (l + r)//2
            if nums[mid]  == target:
                return True

            if nums[l] == nums[mid]:
                l += 1
                continue

            if nums[l] < nums[mid]: # left in order
                if nums[l] <= target < nums[mid]:
                    r = mid
                else:
                    l = mid + 1
            else: # right in order
                if nums[mid] < target <= nums[-1]:
                    l = mid + 1
                else:
                    r = mid
        return False

8 Merge Intervals

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        intervals.sort(key=lambda x: x.start)

        res = []
        for interval in intervals:
            s, e = interval.start, interval.end
            if not res:
                res.append(Interval(s, e))
            else:
                if s > res[-1].end:
                    res.append(Interval(s, e))
                elif s==res[-1].end:
                    res[-1].end = e
                else:
                    res[-1].end = max(res[-1].end, e)
        return res

9 Smallest Range

大概意思就是我们要维护一个pq来存每一列取一个的值，然后pop最小的，然后拿相应列的下一个数来补他的位置。然后把max也要一直存下来。

import heapq
class Solution(object):
    def smallestRange(self, nums):
        """
        :type nums: List[List[int]]
        :rtype: List[int]
        """
        pq = [(row[0], i, 0) for i, row in enumerate(nums)]
        heapq.heapify(pq)

        ans = -1<<31, 1<<31
        right = max(row[0] for row in nums)
        while pq:
            val, i, j = heapq.heappop(pq)
            if right - val < ans[1]-ans[0]:
                ans = val, right
            if j+1 == len(nums[i]):
                return ans
            right = max(right, nums[i][j+1])
            heapq.heappush(pq, (nums[i][j+1], i, j+1))