当前位置：网站首页>leetcode-二分法
leetcode-二分法
2022-06-22 12:31:00 【林冲风雪山神庙】
二分法有两种，一种是有left,right,然后mid等于两者相加再除以2，折半查找。另外一种是在递归的时候折半查找。
二分，left = mid -1;right = mid + 1 ，主要是找指针移动的条件(check函数），根据题意来写check函数，比如爱吃香蕉的可可，要找h 小时内吃掉所有香蕉的最小速度 k，check条件是，当nums[mid]>=target，速度可以缩小。
4.寻找2个正序数组的中位数
34. 在排序数组中查找元素的第一个和最后一个位置
二分开区间的两种写法
左边界：收缩r,另r=mid,用模版1
右边界:收缩l，另l=mid,用模版2
最后返回 r 和返回 l 是一样的，因为循环条件是 while l<r,最后退出的时候两者相等。
class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums.length == 0) return new int[]{-1,-1};
int l = 0, r = nums.length - 1; //二分范围
while( l < r) //查找元素的开始位置
{
int mid = (l + r )/2;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
if( nums[r] != target) return new int[]{-1,-1}; //查找失败
int L = r;
l = 0; r = nums.length - 1; //二分范围
while( l < r) //查找元素的结束位置
{
int mid = (l + r + 1)/2;
if(nums[mid] <= target ) l = mid;
else r = mid - 1;
}
return new int[]{L,r};
}
}
作者：lin-shen-shi-jian-lu-k
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/tu-jie-er-fen-zui-qing-xi-yi-dong-de-jia-ddvc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。#找最左边的下标，和最右边的下标，2次二分 #最左边的下标，当check等于target的时候,收缩右边界,因此可以判断条件是nums[mid]>=target #最右边的下标，当check等于target的时候,收缩左边界，因此可以判断条件是nums[mid]<=target
class Solution:
def searchRange(self, nums, target):
left=0
right=len(nums)-1
#找左边界
while left<right:
mid=(left+right)//2
if nums[mid]>=target:
right=mid
else:
left=mid+1
if nums[right] != target:
return [-1, -1]
a1=right
left = 0
right = len(nums) - 1
# 找右边界
while left < right:
mid = (left + right+1) // 2
if nums[mid] <= target:
left = mid
else:
right = mid-1
a2=left
return [a1,a2]
# nums = [5,7,7,8,8,10]
# target = 8
nums = [5,7,7,8,8,10]
target=6
res=Solution().searchRange(nums,target)
print(res)用都加减一的那种写法
找左边界的时候，判断条件是
nums[mid] >= target，如果nums[mid]大于或者等于target，就往左边移动指针，因为左边还有满足条件的，左边界还没到。
根据判断条件来决定改变哪个边界。
最后一个nums[mid] >= target的mid就是左边界。
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if not nums:
return [-1,-1]
#找左边界
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] >= target:
right = mid - 1
else:
left = mid + 1
if right+1 < len(nums) and nums[right+1] == target:
b1 = right + 1
else:
b1 = -1
#找右边界
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
if left - 1 >=0 and nums[left-1] == target:
b2 = left - 1
else:
b2 = -1
return [b1,b2]2064. 分配给商店的最多商品的最小值
二分板子题
class Solution {
public:
bool check(vector<int> &quantities,int n,int x){
if(x == 0)return false;
int m = quantities.size(),counts = 0;
for(int i = 0; i < m;++i){
counts += ceil((double)quantities[i] / x);
}
return counts <= n;
}
int minimizedMaximum(int n, vector<int>& quantities) {
int left = 0,right = 100000;
while(left < right){
int mid = (right-left)/2 + left;
if(check(quantities,n,mid)){
right = mid;
}else
left = mid+1;
}
return left;
}
};
作者：liyinxin
链接：https://leetcode-cn.com/problems/minimized-maximum-of-products-distributed-to-any-store/solution/c-er-fen-cha-zhao-by-liyinxin-l4f3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
/**
* @param {number} n
* @param {number[]} quantities
* @return {number}
*/
var minimizedMaximum = function(n, quantities) {
let right = Math.max(...quantities);
let left = 1;
while(left <= right) {
let mid = (left + right) >> 1;
if(checked(mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
function checked(num) {
let ans = 0;
for(let i=0; i<quantities.length; i++) {
ans += Math.ceil(quantities[i] / num);
}
return ans <= n;
}
return left;
};
作者：getify
链接：https://leetcode-cn.com/problems/minimized-maximum-of-products-distributed-to-any-store/solution/javascript-zui-da-zhi-zui-xiao-hua-wen-t-rr2v/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。class Solution(object):
def minimizedMaximum(self, n, quantities):
"""
:type n: int
:type quantities: List[int]
:rtype: int
"""
#设分配给商店的最多商品为x
#贪心的想法：quantities[i]/x 得小于等于n。
#找到这个临界值。正好满足quantities[i]/x 得小于等于n
def check(x):
total_cnt = 0
for q in quantities:
cnt = q // x
if q % x != 0:
cnt +=1
total_cnt += cnt
if total_cnt > n:
return False
else:
return True
left=0
right=100000
while left<right:
mid=(left+right)//2
if mid==0:
return 1
if check(mid):
right=mid
else:
left=mid+1
return left
875. 爱吃香蕉的珂珂
二分板子题
class Solution(object):
def minEatingSpeed(self, piles, h):
"""
:type piles: List[int]
:type h: int
:rtype: int
"""
#k满足要求的条件是:piles[i]/k 小于等于8
def check(k):
total_cnt=0
for i in range(len(piles)):
cnt=piles[i]//k
if piles[i]%k>0:
cnt+=1
total_cnt+=cnt
if total_cnt<=h:
return True
return False
left=0
right=10**9
while left<right:
mid=(left+right)//2
if mid==0:
return 1
if check(mid):
right=mid
else:
left=mid+1
return left
用都加减一的那种写法
class Solution(object):
def minEatingSpeed(self, piles, h):
"""
:type piles: List[int]
:type h: int
:rtype: int
"""
def check(x):
count = 0
for i in range(len(piles)):
if piles[i] % x == 0:
count += piles[i] // x
else:
count += piles[i] // x + 1
if count <= h:
return True
else:
return False
left = 1
right = sum(piles)
while left <= right:
mid = (left + right) // 2
#可以吃掉所有香蕉
if check(mid):
right = mid -1
else:
left = mid + 1
return right + 1
2080. 区间内查询数字的频率
二分，找上下界
class RangeFreqQuery {
Map<Integer, List<Integer>> map = new HashMap<>();
public RangeFreqQuery(int[] arr) {
int n = arr.length;
for(int i = 0; i < n; i++){
List<Integer> tmp = map.getOrDefault(arr[i], new ArrayList<>());
tmp.add(i);
map.put(arr[i], tmp);
}
}
public int query(int left, int right, int value) {
if(!map.containsKey(value)) return 0;
int l = lower_bound(map.get(value), left);
int r = upper_bound(map.get(value), right);
return r - l;
}
public int lower_bound(List<Integer> a, int target){
int n = a.size();
int l = 0, r = n;
while(l < r){
int mid = (l + r) >> 1;
if(target <= a.get(mid)) r = mid;
else l = mid + 1;
}
return l;
}
public int upper_bound(List<Integer> a, int target){
int n = a.size();
int l = 0, r = n;
while(l < r){
int mid = (l + r) >> 1;
if(target >= a.get(mid)) l = mid + 1;
else r = mid;
}
return l;
}
}
作者：LCS_0215
链接：https://leetcode-cn.com/problems/range-frequency-queries/solution/ha-xi-biao-er-fen-si-chong-chang-yong-er-nwop/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。class RangeFreqQuery(object):
def __init__(self, arr):
"""
:type arr: List[int]
"""
#记录每个元素出现的下标
self.value_indexs=collections.defaultdict(list)
for i in range(len(arr)):
self.value_indexs[arr[i]].append(i)
def query(self, left, right, value):
"""
:type left: int
:type right: int
:type value: int
:rtype: int
"""
value_index =self.value_indexs[value]
#value index是按照从小到大排列的，
#例如 value index= [2，4，6]。left=3,right=5
cnt=0
for i in value_index:
if i>=left and i<=right:
cnt+=1
return cnt
# Your RangeFreqQuery object will be instantiated and called as such:
# obj = RangeFreqQuery(arr)
# param_1 = obj.query(left,right,value)1060. 有序数组中的缺失元素
注意
if diff[mid] >= k:
right = mid要有等于号，不然有的case通不过。例如
nums = [4,7,9,10] # nums = [1,2,4] k = 3
diff=[0, 2, 3, 3]。得找到第一个3 。
class Solution:
def missingElement(self, nums: List[int], k: int) -> int:
#求出来diff
diff=[0 for _ in range(len(nums))]
for i in range(1,len(nums)):
diff[i]=(nums[i]-nums[i-1]-1)+diff[i-1]
# if diff[i]>=k:
# return nums[i-1]+(k-diff[i-1])
if k>diff[-1]:
return nums[-1]+(k-diff[-1])
#用二分查找k的位置
left=0
right=len(nums)
while left<right:
mid=(left+right)//2
if diff[mid]>=k:
right=mid
else:
left=mid+1
return nums[left-1]+(k-diff[left-1])1182. 与目标颜色间的最短距离
二分板子
用
if left-1>=0:
a2=abs(indexs[left-1]-index)
res.append(min(a1,a2))
来判断是在前面还是后面
class Solution:
def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:
#把元素的索引存成list
from collections import defaultdict
value_index=defaultdict(list)
for i in range(len(colors)):
value_index[colors[i]].append(i)
res=[]
for i in range(len(queries)):
index=queries[i][0]
target=queries[i][1]
if target not in value_index:
res.append(-1)
else:
indexs=value_index[target]
#target和indexs之间的最短距离
left=0
right=len(indexs)-1
while left<right:
mid=(left+right)//2
if indexs[mid]>=index:
right=mid
else:
left=mid+1
a1=abs(indexs[left]-index)
if left-1>=0:
a2=abs(indexs[left-1]-index)
res.append(min(a1,a2))
else:
res.append(a1)
return res1231. 分享巧克力
这个题的难点在于如何判断是不是符合条件，check函数，不好想。
class Solution(object):
def maximizeSweetness(self, sweetness, k):
"""
:type sweetness: List[int]
:type k: int
:rtype: int
"""
def check(thres):
ans = 0
sub_sweetness = 0
for i in range(len(sweetness)):
sub_sweetness += sweetness[i]
if sub_sweetness >= thres:
ans += 1
sub_sweetness = 0
return ans > k
left, right = 1, sum(sweetness)
while left < right:
mid = left + ((right - left + 1) >> 1)
if check(mid):
left = mid
else:
right = mid - 1
return left
作者：mangoooosteen
链接：https://leetcode-cn.com/problems/divide-chocolate/solution/python-er-fen-cha-zhao-by-mangoooosteen-rvz8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。class Solution:
def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
def check(index):
ans=0
count=0
for i in range(len(sweetness)):
count=count+sweetness[i]
if count>=index:
ans+=1
count=0
if ans>=k+1:
return True
return False
left=1
right=sum(sweetness)
while left<=right:
mid=(left+right)//2
if check(mid):
left=mid+1
else:
right=mid-1
return left-1
287 寻找重复数
对值域进行二分
const findDuplicate = (nums) => {
let lo = 1;
let hi = nums.length - 1; //题目注明了：nums.length == n + 1
while (lo < hi) {
const mid = (lo + hi) >>> 1; // 求中间索引
let count = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] <= mid) {
count++;
}
}
if (count > mid) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};
作者：xiao_ben_zhu
链接：https://leetcode-cn.com/problems/find-the-duplicate-number/solution/zhe-ge-shu-zu-you-dian-te-shu-suo-yi-ke-yi-yong-ku/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。【LeetCode-查找】寻找重复数 - Flix - 博客园
写法1
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int left = 1;
int right = nums.size()-1;
while(left<right){
int mid = left+(right-left)/2;
int cnt = 0;
for(int num:nums){
if(num<=mid) cnt++;
}
if(cnt>mid){
right = mid; // 因为是循环条件是left<right，所以这里是 right=mid;
}else{
left = mid+1;
}
}
return left;
}
};写法2
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int left = 1;
int right = nums.size()-1;
while(left<=right){
int mid = left+(right-left)/2;
int cnt = 0;
for(int num:nums){
if(num<=mid) cnt++;
}
if(cnt>mid){
right = mid-1;
}else{
left = mid+1;
}
}
return left;
}
};和爱吃香蕉的可可一样的
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
def check(x):
count = 0
for i in range(len(nums)):
if nums[i] < x:
count += 1
if count < x:
return True
return False
left = 1
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if check(mid):
left = mid + 1
else:
right = mid - 1
#最后一个满足check条件的mid,是left - 1
return left - 1540. 有序数组中的单一元素
奇偶性二分
class Solution {
public int singleNonDuplicate(int[] nums) {
int n = nums.length;
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (mid % 2 == 0) {
if (mid + 1 < n && nums[mid] == nums[mid + 1]) l = mid + 1;
else r = mid;
} else {
if (mid - 1 >= 0 && nums[mid - 1] == nums[mid]) l = mid + 1;
else r = mid;
}
}
return nums[r];
}
}
作者：AC_OIer
链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array/solution/gong-shui-san-xie-er-duan-xing-fen-xi-yu-17nv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。410. 分割数组的最大值
6068. 毯子覆盖的最多白色砖块数
二分找边界
类似的题还有：
436. 寻找右区间
2055.盘子之间的蜡烛
class Solution:
def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
n = len(tiles)
tiles.sort() # 排序
nums = [t[1] for t in tiles] # 瓷砖区间右端点
presum = [r - l +1 for (l,r) in tiles] # 前缀和
presum = list(itertools.accumulate(presum))
ans = 0
for i, (left, _) in enumerate(tiles): # left：毯子左端，right：毯子右端
right = left + carpetLen - 1
j = bisect.bisect_right(nums, right) # 二分搜索【往右搜索】
cnt = presum[j-1] - (presum[i-1] if i >=1 else 0) # [i, j-1]区间内的瓷砖均在毯子覆盖下
if j <= n-1 and right >= tiles[j][0]: # [j]区间内的瓷砖单独判断：
cnt += right - tiles[j][0] + 1 # 毯子右端在[j]区间内
ans = max(ans, cnt)
return ans
作者：flix
链接：https://leetcode.cn/problems/maximum-white-tiles-covered-by-a-carpet/solution/by-flix-zoqe/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。边栏推荐
- 241. Different Ways to Add Parentheses
- 155. Min Stack
- 基于JSP的图书馆管理系统，包含源码，数据库脚本，项目运行视频教程，毕设论文撰写视频教程
- leetcode 1579. 保证图可完全遍历
- MySQL notes
- 448. Find All Numbers Disappeared in an Array
- 基於SSM的小區垃圾分類和運輸管理系統，高質量畢業論文範例（可直接使用），源碼，數據庫脚本，項目導入運行視頻教程，論文撰寫教程
- Using Sqlalchemy for combined paging queries
- SAP system license viewing application and import
- 268. Missing Number
猜你喜欢
建立自己的网站（5）
leetcode-并查集
File download vulnerability & file read vulnerability & file delete vulnerability
剑指 Offer II 114. 外星文字典
别再用 System.currentTimeMillis() 统计耗时了，太 Low，StopWatch 好用到爆！
240. Search a 2D Matrix II
PHP deserialization & Magic method
Pycharm shell script cannot be run
SiCf batch activation service node
重磅直播｜BizDevOps：数字化转型浪潮下的技术破局之路
随机推荐
Application of motion capture system in positioning and mapping of mobile robot in underground tunnel
go语言笔记
leetcode 1579. 保证图可完全遍历
Leetcode 297 match de la semaine
260. Single Number III
47. Permutations II
别再用 System.currentTimeMillis() 统计耗时了，太 Low，StopWatch 好用到爆！
MySQL_ Query of data processing
Windows system installs multiple MySQL versions (without uninstalling the original version), and the old and new versions are compatible.
建立自己的网站（5）
vs code
leetcode 968.监控二叉树
MySQL 5.7 + Navicat 下载安装教程（附安装包）
MySQL中的存储过程
934. Shortest Bridge
476. Number Complement
基于SSM的图书馆管理系统，高质量毕业论文范例（可直接使用），项目导入视频，附送源码和数据库脚本，论文撰写教程
46. Permutations
Testing methodology - data driven testing
Isn't the execution process of ODPs SQL executed from top to bottom