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
