零 前置知识(二分搜索)

二分搜索的关键(我前面文章有讲)
可以先看一下目录 带题目链接 内容有点多哈 但是真的很详细 写了我的思考过程
代码都是AC了的请放心
(由浅入深 一步一步讲)
LeetCode 073->410(难)->牛客机器人跳跃->719(难)
**后续还会更新二分答案算法 **

一 LeetCode LCR 073 爱吃香蕉的狒狒[

LeetCode LCR 073 爱吃香蕉的狒狒

狒狒喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

狒狒可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K
根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉，下一个小时才会开始吃另一堆的香蕉。

狒狒喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

示例 1：

输入: piles = [3,6,7,11], H = 8 输出: 4 示例 2：

输入: piles = [30,11,23,4,20], H = 5 输出: 30 示例 3：

输入: piles = [30,11,23,4,20], H = 6 输出: 23

提示：

1 <= piles.length <= 10^4 piles.length <= H <= 10^9 1 <= piles[i] <=
10^9

1我的思路(下面还有解释 不着急)

每一个速度都会对应一个吃掉所有香蕉所需要的时间
速度越大 吃掉香蕉的时间会不变或者变小
也就是说 速度越大越好
我们假设给定一个速度speed 计算以这个 速度吃完所有香蕉所需要的时间
如果这堆香蕉少于 K

"她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉，下一个小时才会开始吃另一堆的香蕉。 "

这句话的意思时
如果speed 为4
香蕉有3个 需要2个小时
香蕉有5个 需要2个小时
香蕉有4个 需要1个小时
香蕉有2个 需要1 个小时
不难发现 吃完一组香蕉所需要的时间为 (这一组香蕉的个数/speed)向上取整

我们假如speed是固定的 那可以根据piles的值来算出吃完香蕉所需要的时间
3)
这个speed 是有范围的 最小一定是1 最大一定为piles数组中的最大值
(
因为吃掉每一组香蕉至少需要一个小时 是向上取整了
假如 数组最大值为max 以数组最大值为速度speed 吃完所有香蕉所需要的时间一定就是数组长度piles.size()
假如 以比数组最大值还要大的值为speed 那么在吃每一组香蕉时 仍然都是需要一小时 总共需要的时间仍然时数组的长度piles.size() 这一题要求最小值 比数组最大值还要大的speed不用再考虑了 一定时可以吃完的
)
4)
我们可以写一个函数fun() 参数时数组piles 和 速度speed 返回以这个speed为速度吃完所有香蕉需要的时间 具体实现如下

int fun(int speed,vector<int>&piles){
	int time=0;
	for(int it:piles){
		time+=(int)ceil(it*1.0/speed);//*1.0是为了转换为double类型  方便向上取整
	}
	return time;
}

现在我们可以明确一下思路了
speed的范围是 [1,数组最大值max]
速度越大 吃完所需要的时间越小(也可能不变 反正一定不会变小 哈哈)
所以我们可以把speed的取值看作一个数轴 从1开始到max结束
1-----------------max (数轴)
越靠近1越不达标(不达标的意思是不能在指定时间内吃完所有香蕉)
越靠近max越达标(达标的意思是能够在指定时间内吃完所有香蕉)
现在我们已经基本明确了 范围 和 单调性
二分答案

left=1;
right=max;
int mid=(left+right)/2;
//为了避免溢出先减后加 改为int mid=left+(right-left)/2;

如果以mid为速度speed 达标了 那么以更大的速度一定也达标 所以让right=mid-1;
如果以mid为速度speed 不达标 那么以更小的速度一定也不达标 所以让left=mid+1;
最后一定是

[不达标--------------------------------------达标 ]
[------------------right-left-------------------------]

即right右边的数值(不包含right)一定是达标的speed
left左边的数值(不包含left)一定是不达标的speed
这样的话left 一定就是最小的达标的speed了
直接返回left就行了

2 代码实现

我觉得已经说清楚了 谢谢
希望可以帮到你

//AC了
class Solution {
private:
    int fun(int speed,vector<int>&piles){
        int time=0;
        for(int it:piles){
            //必须向上取整 取整之前要转换为double型 所以我*1.0  
            time+=(int)ceil(it*1.0/speed);
            //也可以time+=(int)ceil((double)it/speed);
        }
        return time;
    }    
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int left=1;//左边界
        //直接函数找最大值
        //因为max_element(piles.begin(),piles.end() )返回的是指向最大值的迭代器 
        //所以要加*  解引用
        int right=*max_element(piles.begin(),piles.end() );//右边界
        while(left<=right){//开始二分答案
            int mid=left+(right-left)/2;//先减后加 避免数据溢出
            int time=fun(mid,piles);
            if(time<=h){//如果达标 就是<=要求的时间h
                right=mid-1;//右边界移动
            }else{
                left=mid+1;//左边界移动
            }
        }
        return left;//返回left或者right+1都可以 是一样是数值 哈哈
    }
};

这道题一定要看懂了之后再看下面的题目

3 如果你还是不懂思路(懂了直接跳过)

1)先要明白计算一个speed下 吃完所需要的时间time

“狒狒可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K
根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉，下一个小时才会开始吃另一堆的香蕉。”

这句话的意思是每一堆香蕉吃完它需要的时间一定是大于等于(double)piles[i]/speed个小时 因为如果有剩余时间一定会停下来休息
我们先不管这个h(题目中的条件)所以对于一个给定的速度speed 一定会有一个对应的时间time 表示吃完这个数组的所有香蕉所需要的时间time
函数应该怎么写呢 先说参数 涉及到一个数组piles 一个给定的速度speed

 int fun(vector<int>&piles,int speed){
        int time=0;//计算吃完所有香蕉所需要的时间
        for(int it:piles){//遍历整个数组
            time+=(int)ceil((double)it/speed);//向上取整 
        }
        return time;//返回吃掉所有香蕉所需要的时间
   }
  1. 题目要求在h小时内吃完所有香蕉 我们在函数fun()中传入参数speed 以这个速度speed吃完所有香蕉的时间不一定是小于等于h的
    接下来我们在考虑一个问题 是不是速度越大 这个吃完所有香蕉所需要的时间time越小(或者不变 反正是不会变小的)
    -----假设以一个速度speed吃完所有香蕉所需要的时间是time 如果这个time<=h说明以这个速度speed吃香蕉是达标的(达标就是指满足了题目说的在h小时之内吃完所有香蕉) 那么我们想一想如果以更大的速度吃 香蕉呢 一定也是能在规定时间内吃完的 ok 但是这个题目求的是最小值 所以我们应该探寻一下以比这个speed更小的速度吃香蕉 会不会达标
    -----假设以一个速度speed吃完所有香蕉所需要的时间 是time 如果中国time>h 说明以这个speed速度吃不能在规定时间内吃完所有香蕉 那么我们想一想如果以更小的速度吃呢 那一定也是不能达标的(不达标的意思是不能在规定时间内吃完所有香蕉) 我们就必须要在比speed大的数值上寻找达标的速度
    3)怎么确定speed的范围呢
    speed最小为1
    speed最大是多少呢 ? 因为吃完所有香蕉的时间最大是piles.size() 就是数组的长度 最起码吃一堆香蕉需要一个小时吧 吃完piles.size()堆香蕉最起码需要piles.size()个小时 那么speed最大的就是piles数组中的最大值maxx 因为以更大的值吃香蕉需要的时间也一定是piles.size() 没有讨论的必要了 我们要求的是最小值
    整理一下
left=1;//左边界
right=*max_element(piles.begin(),piles.end() );//右边界

在这个边界上二分 就是** 2 代码实现**上的答案了

二 LeetCode 410 分割数组的最大值(有点难)

LeetCode 410 分割数组最大值

给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组，使得这 k 个子数组各自和的最大值 最小

返回分割后最小的和的最大值。

子数组 是数组中连续的部份。

示例 1：

输入：nums = [7,2,5,10,8], k = 2 输出：18 解释： 一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。 示例 2：

输入：nums = [1,2,3,4,5], k = 2 输出：9 示例 3：

输入：nums = [1,4,4], k = 3 输出：4

提示：

1 <= nums.length <= 1000 0 <= nums[i] <= 106 1 <= k <= min(50,
nums.length)

1 我的思路(有点难 建议自己模拟一下)

1)
我的先明白一个点
如果给定一个子数组的累加和最大值max 用这个max去划分数组 假如最小划分了m个数组 那么一定也能划分m+1 m+2 m+3… 个数组使每一个子数组的累加和小于等于max 这个就是单调性(重要的解题关键)
这个max 越大相当于范围越宽泛 划分的子数组数量就越小
这个max 越大 就越能满足划分的数组数<=k(k 就是题目上的k)
2)
接着
这个子数组的累加和max 是有范围的,最小为0 最大为整个数组的累加和(
因为当累加和最大为整个数组的累加和Sum时
直接可以划分为子数组的数量为1
可以划分为1个子数组满足累加和不大于max
那一定能划分为2个子数组满足累加和不大于max
那一定能划分为3个子数组满足累加和不大于max
那一定能划分为k个子数组满足累加和不大于max…)
3)
所以
只要给定一个字子数组累加和的最大值 我们可以找到最小要把数组划分为几个子数组
这个f()函数 参数为子数组的最大累加和maxx 数组本身nums
返回 最少要划分为多少个子数组part

 int f(vector<int>&nums,int maxx){
 		int part=0;//要分割多少刀 就是间隔
 		int sum=0;//目前中国数组的累加和
 		for(int i=0;i<nums.size();++i){
 			//先不要加进去 先判断加进去之前满不满足 每一部分的累加和<=maxx
 			if(sum+nums[i]>maxx){//如果不满足 就要part++ sum从新开始
 					sum=0;
 					part++;
 			}
 			sum+=nums[i];
 		}
 		part++;//part时切了多少刀 求部分数=part+1
 		return part;
 }

如果这个求出来的部分数part<=k 那么达标(达标的意思是以这个maxx为子数组最大值 分割的数组数一定是小于等于k的) 那么以比这个maxx大的值为子数组最大值 一定也是达标的 所以范围right=mid-1 移动右端点

2 代码实现

//AC了
class Solution {
private:
    //以子数组最大和为max_sum 返回满打满算可以最少分为多少part个数组
    int fun(vector<int>&nums,int max_sum){
        int sum=0;
        int part=1;
        for(int i=0;i<nums.size();++i){
            if(sum+nums[i]>max_sum){//先预处理  看看能不能加上去
                sum=nums[i];//不能加上去就直接更新sum=0 并加上nums[i]
                part++;
            }else{
                sum+=nums[i];//能加上去就直接加上去
            }
        }
        return part;//返回最小被分割为多少部分
    }    
public:
    int splitArray(vector<int>& nums, int k) {
        int left=*max_element(nums.begin(),nums.end() );
        int right=0;
        for(int it:nums)right+=it;
        while(left<=right){
            int midd=left+(right-left)/2;
            int part=fun(nums,midd);
            if(part<=k){//part<=k 意思是以这个midd为子数组的最大和 分割一定是可以分为K个部分的 满足条件
                right=midd-1;//那以更大的标准分割一定也满足条件 我们要找最小值 就缩小右边界
            }else{
                left=midd+1;//缩小左边界
            }
        }
        return left;//right+1也行
    }
};

三 牛客 机器人跳跃问题

机器人跳跃问题

机器人正在玩一个古老的基于DOS的游戏。游戏中有N+1座建筑——从0到N编号，从左到右排列。编号为0的建筑高度为0个单位，编号为i的建筑的高度为H(i)个单位。

起初， 机器人在编号为0的建筑处。每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E,
下一步它将跳到第个k+1建筑。它将会得到或者失去正比于与H(k+1)与E之差的能量。如果 H(k+1) > E 那么机器人就失去
H(k+1) - E 的能量值，否则它将得到 E - H(k+1) 的能量值。

游戏目标是到达第个N建筑，在这个过程中，能量值不能为负数个单位。现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏？

输入描述：
第一行输入，表示一共有 N 组数据.

第二个是 N 个空格分隔的整数，H1, H2, H3, …, Hn 代表建筑物的高度 输出描述：
输出一个单独的数表示完成游戏所需的最少单位的初始能量 示例1 输入： 5 3 4 3 2 4 复制 输出： 4 复制 示例2 输入： 3 4
4 4 复制 输出： 4 复制 示例3 输入： 3 1 6 4 复制 输出： 3 复制 备注： 数据约束： 1 <= N <= 10^5 1
<= H(i) <= 10^5

1 我的思路(二分答案法)

相当于重力势能的问题
遇到比它小的就加上差值 遇到比它大的就减去差值
首先要明白一点 起始值val越大越容易跳跃到最后结尾位置
------当起始值为数组的最大值时 一定能通关(通关就是指能跳到结尾) 因为在遍历的时候遇到的每一个值都会比现在的值小 会加上差值 这个val只会变得越来越大 一定会走到最后通关的
起始值的最小值为0 val为0时不一定能通关
所以就确定了左右边界

int left=0;//左边界
//为什么是arr.begin()+1呢 
//因为看题意 初始值是我们要求的值 也是arr[0] 
//所以接下来要跳跃的值是从arr[1]开始的 
//(注意arr.size()=N+1 设置数组长度的时候要注意)
int right=*max_element(arr.begin()+1,arr.end() );//右边界
  1. 一步一步来思考
    对于每一个起始值 都会产生能不能通关 就是返回true(表示能通关) 还是false(表示不能通关)
bool fun(vector<int>&arr,int val){
		//遍历arr的从下标为1开始
		for(int i=1;i<arr.size();++i){
				val=val+(val-arr[i]);
				if(val<0)return false;//如果出现有负数 直接不通关
		}
		//最后走到这一步(因为<0的时候早就返回false了)一定是>=0 通关
		return true;
}
  1. 不对我们需要考虑一个问题 val=val+(val-arr[i])会不会溢出
    假如val=5 arr数组={ _ ,1 , 1, 1 ,1 , 1,…4,3,2,9,3,4… };
    在前面加的时候+4 =9
    +8 =17
    +16=33
    +32=65
    +64=129
    +128=…
    这样的指数型增加情况一定会溢出(改为long long也会溢出 基本数据类型一定承受不了这样大的数据 )
    因为当val=maxx(maxx就是arr数组的最大值)时 一定会通关(我们之前讲过了) 所以在fun()函数中可以提前返回 保证在溢出前就返回了
    所以fun()函数改为
bool fun(vector<int>&arr,int val){
		int maxx=*max_element(arr.begin()+1,arr.end() );
		//遍历arr的从下标为1开始
		for(int i=1;i<arr.size();++i){
				val=val+(val-arr[i]);
				if(val<0)return false;//如果出现有负数 直接不通关
				if(val>=maxx)return true;//如果>=maxx了 不用管后面的数值了一定会通关的
		}
		//最后走到这一步(因为<0的时候早就返回false了)一定是>=0 通关
		return true;
}

你如果不想每一个调用函数都执行一次*max_element(arr.begin()+1,arr.end() );
就改为传参数

bool fun(vector<int>&arr,int val,int maxx){
		//遍历arr的从下标为1开始
		for(int i=1;i<arr.size();++i){
				val=val+(val-arr[i]);
				if(val<0)return false;//如果出现有负数 直接不通关
				if(val>=maxx)return true;//如果>=maxx了 不用管后面的数值了一定会通关的
		}
		//最后走到这一步(因为<0的时候早就返回false了)一定是>=0 通关
		return true;
}

我更偏向于传参数 哈哈

4 ) 本质上就是确定范围和单调性

2 我的代码

思路很清晰 可读性强
ACM模式输入输出

//AC了
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool fun(vector<int>&arr,int val,int maxx){
    for(int i=1;i<arr.size();++i){
        val=val+(val-arr[i]);//加上差值 如果val-arr[i]<0就相当于减去了差值的绝对值 是一样的
        if(val<0)return false;//出现负数 直接不通关
        if(val>=maxx)return true;//出现>=maxx 不用再管后面的了一定会通关的
    }
    return true;//都走到这一步了 一定通关
}
int main() {
    int N;
    cin >> N;
    vector<int>arr(N + 1); //注意要设置为N+1 不懂的话看看题目要求
    for (int i = 1; i <= N; ++i)cin >> arr[i];
    int left = 0;//左边界
    int maxx = *max_element(arr.begin() + 1, arr.end() );//数组舍弃arr[0]后的最大值
    int right = maxx;//右边界
    while (left <= right) {//二分答案
        int midd = left + (right - left) / 2;
        if (fun(arr, midd, maxx) == true ) {//如果以midd为起始值通关 那么以大于它的也一定通关 
            right=midd-1;//我们要找刚好通关的最小值 所以要缩小右边界
        }else{
            left=midd+1;//缩小左边界
        }
    }
    cout<<left<<endl;//cout<<right+1<<endl;也行 一样的
}

四 LeetCode 719 找出第k 小的数对的距离(难题)

LeetCode 719

数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。

给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j <
nums.length 。返回 所有数对距离中 第 k 小的数对距离。

在这里插入图片描述

示例 1：

输入：nums = [1,3,1], k = 1 输出：0 解释：数对和对应的距离如下： (1,3) -> 2 (1,1) -> 0
(3,1) -> 2 距离第 1 小的数对是 (1,1) ，距离为 0 。 示例 2：

输入：nums = [1,1,1], k = 2 输出：0 示例 3：

输入：nums = [1,6,1], k = 3 输出：5

提示：

n == nums.length 2 <= n <= 104 0 <= nums[i] <= 106 1 <= k <= n * (n -1) / 2

1 我的思路

这个距离是由范围的最小是0 最大是maxx-minn 距离不会超出数组最大值于最小值的差值
[0 , maxx-minn]

int left=0;
int maxx=*max_element(nums.begin(),nums.end() );
int minn=*min_element(nums.begin(),nums.end() );
int right=maxx-minn;

fun()函数返回小于等于limit 的数对数量cnt
如果这个数对数量cnt<=k 那么以更大的limit传入fun()函数 返回的一定比cnt要大 就一定不是第k小的差值了
如果这个数对数量cnt>k 那么这个limit一定不是第k小的差值 比它小的limit也一定不是第k小的差值 一定是大于k的

2 代码实现

//AC了
class Solution {
public:
		//返回数组中小于等于limit的数对数量cnt 
		//用滑动窗口法(时间复杂度为O(n) 只遍历一遍数组)
    int fun(vector<int>&nums,int limit){
        int left=0;
        int cnt=0;
        for(int right=left+1;right<nums.size();++right){
            while(nums[right]-nums[left]>limit){
                left++;
            }
            cnt+=(right-left);//以right为结束的数对数量正好就是right-left
        }
        return cnt;
    }
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end() );
        int left=0;//左边界
        int maxx=*max_element(nums.begin(),nums.end() );
        int minn=*min_element(nums.begin(),nums.end() );
        int right=maxx-minn;//右边界
        while(left<=right){
            int midd=left+(right-left)/2;
            int cnt=fun(nums,midd);
            if(cnt>=k){//cnt就是以差值小于等于midd的数对数量
            				 //cnt就是以midd为答案的排序后序号
                right=midd-1;
            }else{
                left=midd+1;
            }
        }
        return left;
    }
};
# leetcode # 算法 # 职场和发展 # 数据结构
Logo
DAMO开发者矩阵

DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐

工业机器人离线编程基础与 ABB RobotStudio 软件实操

工业机器人编程方法主要包括示教编程和离线编程两种主流方式。示教编程需现场操作机器人记录轨迹，而离线编程通过虚拟环境进行三维建模与仿真，具有不占用生产时间、支持复杂轨迹等优势。国内外主流离线编程软件分为专用型（如ABB RobotStudio、FANUC RoboGuide）和通用型（如RobotMaster、国产PQArt），正朝着智能化、专用化方向发展。文章重点介绍了ABB RobotStudi

avatar DAMO开发者矩阵
cover

人形机器人手指关节选材：铝合金 vs PEEK，谁才是轻量化的终极方案？

avatar DAMO开发者矩阵
cover

硬实时·强生态：鸿道Intewell硬实时操作系统

avatar DAMO开发者矩阵