【二分答案法】Leetcode相关题目解析

题目:162. 寻找峰值 - 力扣(LeetCode)

题目描述:

        

题目分析:

        (1)据题知,索引-1、索引n(n为数组长度)处的元素都默认为无穷小,我们可以在一开始特判一些简单情况:当数组长度等于1时,直接返回0;当索引0处的元素大于索引1处的元素时,直接返回0;当索引n - 1处的元素大于索引n-2处的元素时,返回n - 1。

        (2)如果给定的数组不满足特判条件,用折线来描述这个数组的升降,一定能找到一个峰值元素,如下图所示。

        索引0到索引1是上升趋势,索引n-2到索引n-1是下降趋势,由于数组不存在重复元素,所以无论你怎么拼接这条折线,中间一定有一个峰值元素。

        (3)假设我们二分到一个元素nums[m],有三种情况:1、nums[m]就是峰值元素,更新答案,退出循环;2、nums[m-1] > nums[m],这里呈下降趋势,而索引0到索引1是上升趋势,所以在0 到 m - 1这个区间肯定有一个峰值元素,right = m - 1往左侧二分;3、nums[m+1] > nums[m],这里呈上升趋势,而索引n - 2到索引n - 1是下降趋势,所以在m + 1 到 n - 2这个区间肯定有一个峰值元素,left = m + 1往右侧二分。

Code:

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        
        //数组中只有一个元素,直接返回0
        if(n == 1)
        return 0;
        
        //索引0处的元素满足要求,返回0
        if(nums[0] > nums[1])
        return 0;
        
        //索引n - 1处的元素满足要求,返回n - 1
        if(nums[n - 1] > nums[n - 2])
        return n - 1;

        int left = 1,right = n - 2;
        int ans = 0;
        while(left <= right){
            int m = left + (right - left) / 2;
            
            //nums[m-1] > nums[m],这里是下降趋势
            //那么答案一定在左侧,往左侧二分
            if(nums[m - 1] > nums[m]){
                right = m - 1;
            }
            //nums[m+1] > nums[m],这里是上升趋势
            //答案一定在右侧,往右侧二分
            else if(nums[m + 1] > nums[m]){
                left = left + 1;
            }else{
                //nums[m+1]和nums[m-1]都不大于nums[m]
                //那么nums[m]就是峰值元素
                ans = m;
                break;
            }
        }
        return ans;
    }
}

题目:875. 爱吃香蕉的珂珂 - 力扣(LeetCode)

题目描述:

题目分析:

        (1)题目给你piles.length堆香蕉,第i堆香蕉的数量为piles[i],如果珂珂吃香蕉的速度k(单位是小时)大于香蕉数piles[i],吃完她会停下休息;如果速度k等于piles[i],吃完她不会休息会继续吃下一堆香蕉;如果速度k小于piles[i],比如k = 2,piles[i] = 7,她吃完这堆香蕉需要4小时,因为每次吃完香蕉如果还有剩余时间她会选择休息。

        (2)题目给定的堆数piles.length小于管理员离开的时间h,意味着珂珂总能以一个速度k在管理员回来之前吃完所有香蕉。同时piles[i] >= 1,表示每堆香蕉至少有一根香蕉。

        (3)分析完题目,我们来预估答案的范围。答案最小可以是1,因为piles数组可能是这种形式:[1,1,1,1,1]答案最大不会超过最大香蕉数,假设piles为:[2,3,5,100,79],最大香蕉数是100,如果管理员离开的时间是5(不会小于香蕉堆数),那么此时珂珂吃香蕉的速度必须大于等于100才有可能在管理员回来之前吃完所有香蕉。101、102……等速度虽然也能在规定时间内吃完所有香蕉,但不符合题目要求的最小速度。

        (4)如果珂珂能以速度k在规定时间内吃完香蕉,那么她以速度k + 1、k + 2肯定也能在规定时间内吃完所有香蕉,此时我们往左侧二分寻找更小的速度(速度满足要求,要寻找更小的速度);如果珂珂以速度k不能在规定时间内吃完香蕉,那么她以速度k - 1、k - 2肯定也无法在规定时间内吃完所有香蕉,此时我们往右侧二分寻找符合要求的答案(速度不满足要求,要满足要求的速度)。

Code:

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int n = piles.length;

        //答案范围在:[1,最大香蕉数]之间
        int left = 1,right = 0;

        for(int pile : piles)
        right = Math.max(pile,right);

        int ans = 0;
        while(left <= right){
            int m = left + (right - left) / 2;

            //如果以速度m能在规定时间内吃完香蕉
            //那么以比m大的速度吃香蕉,肯定也能在规定时间内吃完
            if(prove(m,piles,h)){
                //记录答案,并往左侧二分
                right = m - 1;
                ans = m;
            }else{
                //否则往右侧二分
                left = m + 1;
            }
        }
        return ans;
    }

    private boolean prove(int speed,int [] piles,int h){
        //由于piles[i] <= 10^,防止整型溢出,用long
        long hour = 0;

        for(int pile : piles){
          //如果速度大于等于香蕉数,那么只需要1小时足以
          if(speed >= pile)
          hour++;
          //如果速度小于香蕉数,则需要(pile / speed)向上取整
          else
          hour += (pile + speed - 1) / speed;//这里是向上取整的写法
        }
        //最后判断以速度speed吃香蕉,是否能在规定时间内吃完
        return hour <= h;
    }
}

题目:410. 分割数组的最大值 - 力扣(LeetCode)

题目描述:

题目分析:

        (1)题目给定一个非负整数数组nums和一个整数k,要求将数组nums分成k个连续子数组,使得这k个子数组和的最大值最小。

        (2)将题目抽象成画家问题:给你一个整数数组nums,nums[i]代表画第i副画所需要的时间,同时给你k个画家并行作画,每个画家只能画连续的画(不能nums[i]、nums[i + 2]这样跳跃式的作画),问如果画家同时作画,如何分配画家能使得画完所有画所需的时间最少。

        图解:

        (3)来预估答案的范围,答案最小可能是0,因为题目提示:nums[i] >= 0,nums数组有可能是:[0,0,0,0,...]这种形式;答案最大可能是数组总和,有可能题目给定k = 1,只有一个画家,那么他画完所有画需要的时间就是数组总和。

        (4)定义一个验证函数prove(int [ ] nums,int value),函数定义:将nums数组拆分成多个子数组,要求每个子数组的和 <= value,返回子数组个数。在使用二分前先来达成一个共识:value越大,子数组能容纳的元素越多,能拆分nums数组得到的子数组个数就越少;value越小,子数组能容纳的元素越少,能拆分nums数组得到的子数组个数就越多。

        (5)基于上述共识,如果一个值value能拆分的子数组个数 <= k(题目要求的子数组个数),那么比value大的数能拆分的子数组个数肯定也 <= k;如果一个值value能拆分的子数组个数 > k,那么比value小的数能拆分的子数组个数肯定也 > k。

Code:

class Solution {
    public int splitArray(int[] nums, int k) {

        //答案范围:[0,数组总和]
        int left = 0,right = 0;

        for(int n : nums)
        right += n;

        int ans = 0;
        while(left <= right){
            int m = left + (right - left) / 2;

            //如果分得的子数组个数<=k
            if(prove(nums,m) <= k){
                
                //满足题目要求,更新答案
                //并往左侧二分,看有没有更小的值符合要求
                ans = m;
                right = m - 1;
            }else{
                //如果子数组个数 > k
                //不符合题目要求,往右侧二分,寻找满足要求的答案
                left = m + 1;
            }
        }
            return ans;
    }
    
    //函数定义:将nums数组拆分成多个子数组,要求每个子数组的和<=value,返回子数组个数
    //如果拆分不了就返回整型最大值
    public int prove(int [] nums,int value){
        //bucket变量代表子数组个数
        int bucket = 1;
        int sum = 0;

        for(int num : nums){
            //元素值num > value,拆分不了
            if(num > value){
                return Integer.MAX_VALUE;
            }
            
            //往子数组中纳入元素
            sum += num;
            //发现子数组和 > value时
            if(sum > value){
                //bucket++,并让sum从当前元素开始累加,代表生成一个新的子数组
                bucket++;
                sum = num;
            }
        }
        return bucket;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/232369.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

软件设计师——操作系统(一)

&#x1f4d1;前言 本文主要是【操作系统】——软件设计师——操作系统的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是听风与他&#x1f947; ☁️博客首页&#xff1a;CSDN主页听风与他 &#x1f304…

鸿蒙开发组件之ForEach列表

一、ForEach函数 ForEach函数是一个迭代函数&#xff0c;需要传递两个必须参数和一个可选参数。主要通过迭代来获取参数arr中的数据不断的生成单个Item来生成鸿蒙中的列表样式 二、先创建单个的Item的UI 通过嵌套Row与Column来实现单个Item的UI。例如图中没有折扣的可以看成一…

Pandas中DataFrame对象的创建与常用属性方法(第2讲)

Pandas中DataFrame对象的创建与常用属性方法(第2讲)         🍹博主 侯小啾 感谢您的支持与信赖。☀️ 🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔…

【Docker】swarm stack部署多service应用

前面我们已经学习过了Docker Compose&#xff0c;它可以用来进行一个完整的应用程序相互依赖的多个容器的编排的&#xff0c;但是缺点是只能在单机模式使用&#xff0c;不能在分布式多机器上使用&#xff1b;前面我们也学习了Docker swarm&#xff0c;它可以将单个服务部署为多…

鸿蒙生态开发就业前景到底好不好

鸿蒙生态开发是指基于华为自主研发的操作系统鸿蒙&#xff08;HarmonyOS&#xff09;进行应用程序开发和生态建设。目前&#xff0c;鸿蒙生态开发的前景非常好&#xff0c;原因如下&#xff1a;做鸿蒙应用开发到底学习些啥&#xff1f; (qq.com) 1&#xff1a;政府支持&#x…

万界星空科技mes系统中看板管理

我们很多企业现在都有大屏&#xff0c;那到底万界星空科技低代码云mes系统管理中看板管理有什么作用&#xff1f;我总结了几条: 1.提高车间的生产效率 2.有效的监控设备运行状况 3.控制生产线运行 4.增加和改善用户体验 5.提高工作效率和工作安全性

综述 2019-Genome Biology:非比对方法的benchmark

Zielezinski, Andrzej, et al. "Benchmarking of alignment-free sequence comparison methods." Genome biology 20.1 (2019): 1-18. Benchmarking of alignment-free sequence comparison methods | Genome Biology | Full Text 被引次数&#xff1a;170&#xff…

【算法通关村】链表反转经典问题解析

&#x1f6a9;本文已收录至算法学习之旅 一.基础反转 我们通常有两种方法反转链表&#xff0c;一种是直接操作链表实现反转操作&#xff0c;一种是建立虚拟头节点辅助实现反转操作。 力扣习题链接&#xff1a;206. 反转链表 (1) 直接操作实现反转 我们需要一个变量pre来保…

代码随想录算法训练营第45天| 139.单词拆分 多重背包

JAVA代码编写 139.单词拆分 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 **注意&#xff1a;**不要求字典中出现的单词全部都使用&#xff0c;并且字典中的单词可以重复使用。 示例 1&#xff1a; 输入: s &…

如何利用人工智能+物联网技术实现自动化设备生产

随着科技的发展与行业竞争的日益激烈&#xff0c;制造业也逐渐走向智能化发展。制造业的改革是利用物联网技术和自动化设备&#xff0c;实现生产线的智能化和自适应生产&#xff0c;优化生产流程&#xff0c;提高生产效率和质量&#xff0c;为企业创造更大的价值。 方案概述 智…

Linux 压缩、文件传输与安装

目录 1. 压缩 1.1 tar 1.2 gzip 1.3 zip 1.4 rar 2 文件传输 2.1 网站下载 2.2 scp 传输 2.3 rz 和 sz 2.4 xftp 3.安装 3.1 编译安装 &#xff08;ngnix&#xff09; 3.2 rpm 安装 3.3 yum 安装 1. 压缩 1.1 tar 使用 tar 压缩文件时&#xff0c;会保留源文件…

使用MetaMask + Ganache搭建本地私有网络并实现合约部署与互动

我使用Remix编写合约&#xff0c;MetaMask钱包工具和Ganache搭建了一个私有网络&#xff0c;并且实现了合约的部署和互动。 在前面的博客中提到了 Remix在线环境及钱包申请 以及 Solidity的基本语法 &#xff0c;没看过的小伙伴可以点击链接查看一下&#xff0c;都是在本专栏下…

智能时代:互联网+如何改变我们的生活与工作

引言 随着科技的不断进步和互联网的普及&#xff0c;我们正处在一个智能时代。这个时代被互联网所定义&#xff0c;它深刻地改变了我们的生活和工作方式。从社交互动到日常工作&#xff0c;智能时代的影响无处不在&#xff0c;给人们带来了前所未有的变革和机遇。 互联网的涌…

模电·放大电路的分析方法——图解法

放大电路的分析方法——图解法 静态工作点的分析电压放大倍数的分析波形非线性失真的分析直流负载线与交流负载线图解法的适用范围 在实际测出放大管的输入特性、输出特性和已知放大电路中其它各元件参数的情况下&#xff0c;利用作图的方法对放大电路进行分析即为图解法。 静…

FacetWP WordPress网站高级筛选过滤插件(含所有扩展)

点击阅读FacetWP WordPress网站高级筛选过滤插件原文 FacetWP WordPress网站高级筛选过滤插件向电子商务网站、资源库、搜索页面等添加分面搜索。FacetWP 的过滤元素&#xff08;称为 facets&#xff09;动态调整以适应用户输入。这有助于防止出现“未找到结果”&#xff0c;从…

OpenSSL 编程指南

目录 前言初始化SSL库创建SSL 上下文接口(SSL_CTX)安装证书和私钥加载证书(客户端/服务端证书)加载私钥/公钥加载CA证书设置对端证书验证例1 SSL服务端安装证书例2 客户端安装证书创建和安装SSL结构建立TCP/IP连接客户端创建socket服务端创建连接创建SSL结构中的BIOSSL握手服务…

【MATLAB源码-第99期】基于matlab的OFDM系统卡尔曼滤波(kalman)信道估计,对比LS,MMSE。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 卡尔曼滤波器&#xff08;Kalman Filter&#xff09;是一种有效的递归滤波器&#xff0c;它能够从一系列的含有噪声的测量中估计动态系统的状态。在无线通信领域&#xff0c;尤其是在正交频分复用&#xff08;OFDM&#xff0…

Pandas中的Series(第1讲)

Pandas中的Series(第1讲)         🍹博主 侯小啾 感谢您的支持与信赖。☀️ 🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔…

Redis基础入门

第1章&#xff1a;引言 大家好&#xff01;我是小黑&#xff0c;今天咱们来聊聊Redis。Redis&#xff0c;这个名字你可能在不少地方听过&#xff0c;尤其是在后端开发领域&#xff0c;它可是个大名鼎鼎的角色。&#xff0c;Redis是一个开源的内存中数据结构存储系统&#xff0…

利用jdbc对数据库进行增删改查

步骤/过程&#xff1a; 1&#xff0c;导入驱动包 2&#xff0c;加载驱动包 3&#xff0c;输入信息&#xff0c;进行数据库连接 4&#xff0c;创建 statement对象 5&#xff0c;执行sql语句 6&#xff0c;如果是查询操作&#xff0c;利用ResultSet处理数据&#xf…