欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 科技 > 能源 > 二分算法 (二)

二分算法 (二)

2025/3/17 6:57:21 来源:https://blog.csdn.net/weixin_74850661/article/details/145380307  浏览:    关键词:二分算法 (二)

文章目录

  • 题目总览
  • 题目详解
    • 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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com