2020-2-17 刷题记录

0X00 leetcode 做了 4 道

• 74 Search a 2D Matrix
• 530 Minimum Absolute Difference in BST
• 1011 Capacity To Ship Packages Within D Days
• 875 Koko Eating Bananas

0X01 每道题的小小总结

74 Search a 2D Matrix

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if matrix is None or len(matrix) == 0 or len(matrix[0]) == 0 or target < matrix[0][0]:
            return False
        
        top, bottom = 0, len(matrix) - 1
        while top < bottom:
            mid = top + (bottom - top) // 2
            if matrix[mid][0] == target:
                return True
            elif matrix[mid][0] > target:
                bottom = mid - 1
            else:
                if target ==  matrix[mid][-1]:
                    return True
                elif target < matrix[mid][-1]:
                    top = bottom = mid
                else:
                    top = mid + 1

        left, right = 0, len(matrix[top]) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if matrix[top][mid] == target:
                return True
            elif matrix[top][mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        
        return False

这道题我肯定不是最优解,用两次二分搜索找到答案

其实矩阵也有一些模板,这道题的最优解应该涉及一个模板,我现在没总结下来,我先完成第一阶段的 300 道题目再说

530 Minimum Absolute Difference in BST

这里设计一个性质:

就是二叉搜索树的中序遍历是这个树的所有元素的排序,而且最小之差,肯定就是这个排序的相邻元素的差的最小值

不是最优解

class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        order = []
        def helper(root):
            if root is None: return
            helper(root.left)
            order.append(root.val)
            helper(root.right)
            return root.val 
        helper(root)

        ans = float("inf")
        for i in range(1, len(order), 1):
            ans = min(order[i] - order[i-1], ans)

        return ans

1011 Capacity To Ship Packages Within D Days

接下来两道题就是模板了

二分搜索:

• 从最小值到最大值之间不断二分

• 满足某种性质,左边 = mid + 1

• 否则 右边 = mid

不是最优解,代码写得比较烂

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:

        def possible(c):
            d = 0
            s = 0
            idx = 0
            while idx < len(weights):
                s += weights[idx]
                if s > c:
                    s = 0
                    d += 1
                    idx -= 1
                elif s == c:
                    s = 0
                    d += 1
                idx += 1
            return d < D

        l, h = max(weights), sum(weights)
        while l < h:
            m = l + (h - l) // 2
            if not possible(m):
                l = m + 1
            else:
                h = m
        
        return l
            

875 Koko Eating Bananas

上面模板改的:

class Solution:
    def minEatingSpeed(self, piles: List[int], H: int) -> int:
        def possible(k):
            return sum([((p-1) // k) + 1 for p in piles]) <= H

        l, h = 1, max(piles)

        while l < h:
            k = l + (h - l) // 2
            if not possible(k):
                l = k + 1
            else:
                h = k
        return l