剑指 Offer II 二分查找
2024-10-21 11:47:33
068. 查找插入位置
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l=0,r=nums.size();
nums.push_back(1000000);//一定有数比target大 它在的位置会是最后一个插入的位置 可以直接return l
while(l<r)
{
int mid=l+r>>1;
if(nums[mid]>=target)r=mid;
else l=mid+1;
}
return l;
}
};
069. 山峰数组的顶部
山峰符合两段性
class Solution {
public:
int peakIndexInMountainArray(vector<int>& a) {
int l=1,r=a.size()-2;
while(l<r)
{
int mid=l+r+1>>1;
if(a[mid]>a[mid-1])l=mid;
else r=mid-1;//说明答案严格在左侧
}
return l;
}
};
070. 排序数组中只出现一次的数字
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
/*
二分的性质是 两两看成一组
target左边 数都相同
右边 数都不同
*/
nums.push_back(nums.back()+1);
int l=0,r=nums.size()/2-1;//组数
while(l<r)
{
int mid=l+r>>1;
if(nums[mid*2]==nums[mid*2+1])l=mid+1;//在左边
else r=mid;
}
return nums[2*l];//第l组第一个数
}
};
071. 按权重生成随机数
class Solution {
public:
/*
二分查前缀和 下标
*/
vector<int>s;
Solution(vector<int>& w) {
s=w;
for(int i=1;i<w.size();i++)s[i]+=s[i-1];
}
int pickIndex() {
int x=rand()%s.back()+1;//1到s.back()
return lower_bound(s.begin(),s.end(),x)-s.begin();
}
};
072. 求平方根
class Solution {
public:
int mySqrt(int x) {
int l=0,r=x;
//第一个y^2<=x
while(l<r)
{
int mid=l+r+1ll >>1; //LL类型的1
if(mid<=x/mid)l=mid;
else r=mid-1;
}
return l;
}
};
073. 狒狒吃香蕉
二分的是答案
class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
int l=1,r=1;
for(auto x:piles)r=max(r,x);
while(l<r)
{
int mid=l+r>>1;
int time=0;
for(auto x:piles)time+=(x+mid-1)/mid;
if(time<=h)r=mid;
else l=mid+1;
}
return l;
}
};
最新文章
- 9.Configure One-to-One（配置一对一关系）【Code-First系列】
- WCF Failed to invoke the service. Possible causes: The service is offline or inaccessible
- 30天C#基础巩固------集合，File(文件操作 ),Encoding处理字符集
- hiho #1284 机会渺茫
- javascript 分页组件
- MongoDB增删改查
- （7）nehe教程1 创建一个OpenGL窗口:
- IOS 中关于自定义Cell 上的按钮 开关等点击事件的实现方法（代理）
- CocoaPods 安装使用教程
- Tinyhttpd精读解析
- python 模块与包
- Java异常实战——OutOfMemoryError
- svg 动画 透明度 放大缩小 x轴Y轴
- 孟岩：怎么看待Coin与Token的关系？
- HTML特殊符号（字符实体)大全
- luogu 1484\1792 种树 奇怪的贪心可反悔
- Eclipse块选择快捷键
- .NET Core 配置GC工作模式与内存的影响
- IDEA出现Cannot resolve symbol "xxx"(无法解析符号)
- 总结我在huawei matebook D 2018版中安装archlinux的过程