文章目录
- 题目总览
- 题目详解
- 3143.正方形中的最多点数
- 410.分割数组的最大值
- 3281.范围内整数的最大得分
题目总览
二分作为求解答案的一种中间手段
关键在于这个check函数的定义,其中的话,大多数使用到贪心,因为是二分,会一步步接近这个结果,所以开始的范围大一点没有关系
最小化最大值和最大化最小值,首先想到这个二分算法
二分作为中间手段
3143.正方形中的最多点数
最小化最大值
410.分割数组的最大值
最大化最小值
3281.范围内整数的最大得分
题目详解
3143.正方形中的最多点数
思路分析:
可以看到边长的范围很长,所以使用暴力是不可能在规定时间内求解的,由于边长的变化可以单调,所以我们可以以边长为变量进行使用二分求解,对于每一次得到的mid
,我们再逐一判断是否有重复的元素(使用集合进行判断
)
class Solution:def maxPointsInsideSquare(self, points: List[List[int]], s: str) -> int:ans = 0def check(mid):vis = set()for (x,y),c in zip(points,s):if abs(x) <= mid and abs(y) <= mid:if c in vis:return Falsevis.add(c)nonlocal ans ans = len(vis)return Trueleft ,right = 0,1000_000_000while left<=right:mid = (left+right)//2# 满足条件if check(mid):left=mid+1else:right=mid-1return ans
410.分割数组的最大值
思路分析
:根据灵神的思路,
难点还是在于如何统计这个段数,其实只要我们从左往右,根据你传入的这个mid的值,根据是否能够累加得到,如果超过这个mid 值,则多开一段
当然,我们求解的是 这个最小的最大值,那我们就可以以这个为变量进行二分求解
class Solution:def splitArray(self, nums: List[int], k: int) -> int:ans = 0def check(mid):numk , s = 1,0for i in nums:if s + i <= mid:s += ielse:# 新开一段numk+=1s = i if numk>k:return Falsenonlocal ansans = midreturn Trueleft,right = max(nums),sum(nums)# 单调性的体现,对于最大值的最小,当你划分的k越小,则越大while left<=right:mid = (left+right)//2# 如果满足条件,则可以变小看看if check(mid):right=mid -1else:left=mid +1return left
3281.范围内整数的最大得分
思路分析
:关键点还是在于check函数的定义,在这里是判断是否满足对于选择的数字是否满足这个区间的要求
class Solution:def maxPossibleScore(self, start: List[int], d: int) -> int:# 先按照升序排序start.sort()# check函数是使用贪心策略来构建的def check(mid):s = start[0]for i in range(1,len(start)):# if start[i] <= s + mid and s+mid <= start[i]+d:# 这个s+mid 不一定大于start[i]if s+mid <= start[i]+d:s = max(start[i],s +mid)else:return Falsereturn Trueleft,right = 0, 2000_000_001# 贪心思想,如果此时的mid满足,表示至少可以满足while left<=right:mid = (left+right)//2if check(mid):left=mid+1else:right=mid-1return right