二分法题集2

目录

1  山脉数组的峰顶索引

分析:

代码展示:

2 寻找峰值

分析:

代码展示:

3  寻找旋转排序数组中的最小值

分析:

代码展示:

4 点名

分析:

代码展示:


1  山脉数组的峰顶索引

分析:

我们前面说过只要是有二段性的就可以用二分法。这道题时间复杂度要求是logn那么也在提示我们用二分法做。前面几道题大家可以很容易想到如何二分,而这道题及后面的题难点在于如何找出题的二段性,只要找出规律那么题解模板都是一样的。

这道题中题目给了我们思路,目标值的左边均是递增,目标值的右边均是递减,那么我们就可以根据递增递减作为二分依据,然后就可以将题目转换为找出数组中最后一个递增的下标(同理我们也可以转换为找出第一个递减的下标)。

代码展示:


以找出最后一个递增下标为例

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 1;
        int right = arr.length - 2;
        while(left < right) {
            int middle = left + (right - left + 1) / 2;
            if(arr[middle] < arr[middle - 1]) {
                right = middle -1;
            }else {
                left = middle;
            }
        }
        return left;
    }
}

只要当前值存在于递减序列,那我们就让right = middle - 1,那么right最后指向的一定是最后一个递增下标。

由于题目中说,数组一定是山峰数组,所以数组0和最后一个下标一定不是目标值,所以我们将 left = 0 ,right = arr.length - 2即可。

以找出第一个递增下标为例

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 1;
        int right = arr.length - 2;
        while(left < right) {
            int middle = left + (right - left) / 2;
            if(arr[middle] < arr[middle + 1]) left = middle +1;
            else right = middle;
        }
        return left;
    }
}
2 寻找峰值

分析:

这道题个上道题的不同点:

1 数组中左右边界值都是无穷小,因此我们可以理解为,递增数组的最后一个值就是峰值,递减数组的第一个值就是峰值;

2 该数组中存在多个峰值,但只需要返回其中一个即可。

代码展示:
class Solution {
    public int findPeakElement(int[] arr) {
        if(arr.length < 2) return 0;
         int left = 0;
        int right = arr.length - 1;
        while(left < right) {
            int middle = left + (right - left) / 2;
            if(arr[middle] < arr[middle + 1]) left = middle +1;
            else right = middle;
        }
        return left;

    }
}

代码和上一道题的基本没有变化,虽然存在多个峰值,但是因为我们的left是小于right也就保证了我们一定可以求出一个峰值。

3  寻找旋转排序数组中的最小值

分析:

这道题让我们用longn的算法解决,那么我们就要去想到二分。接下来我们要找到这道题的二分性。我们可以发现如果选取数组第一个值为参考时,则最小值到该数区域内均大于该数,最小值到数组末尾均小于该数,那么我们就可以转换为找出第一个小于数组0小标值的元素。当然如果第一个数就是最小数,那么我们结尾分情况讨论。当找出二分性的依据之后,那代码和之前的没有什么变化

代码展示:
class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int tmp = nums[left];
        while(left < right) {
            int middle = left + (right - left ) / 2;
            if(nums[middle] >= tmp){
                left = middle + 1;
            }else {
                right = middle;
            }
        }
        if(nums[left] < tmp)
        return nums[left];
        else return nums[0];

    }
}
4 点名

分析:

这道题我们可以用二分法做:

二分依据:下标值等于对应的数组值和下标值不等于对应的数组值。这样问题就转换为找出第一个下标值与对应值不匹配的数,那么left = middle + 1一定会指向这个数。

代码展示:
class Solution {
    public int takeAttendance(int[] records) {
        int left = 0;
        int right =records.length;
        while(left < right) {
            int middle = left + (right - left) / 2;
            if(records[middle] == middle ) {
                left = middle + 1;
            }else {
                right = middle;
            }
        }
        return left;

    }
}

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

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

相关文章

数据结构学习——栈和队列

1.栈 1.1栈的概念及结构 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO&#xff08;Last In First Out&#xff09;的原则。 …

《BERT》论文笔记

原文链接&#xff1a; [1810.04805] BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding (arxiv.org) 原文笔记&#xff1a; What&#xff1a; BETR&#xff1a;Pre-training of Deep Bidirectional Transformers for Language Understand…

Ruoyi-vue-pro Vue + nginx 二级目录部署到云服务器

http://www.your-server.com/ 这是一级目录&#xff0c;由于项目多&#xff0c;一般会通过二级域名http://oa.your-server.com/或二级目录http://www.your-server.com/oa来发布&#xff0c;本篇记录一下二级目录发布。先看效果 1、router/index.js配置base export default new …

对代理模式的理解

目录 一、前言二、案例1 代码2 自定义代理类【静态代理】2.1 一个接口多个实现&#xff0c;到底注入哪个依赖呢&#xff1f;2.1.1 Primary注解2.1.2 Resource注解&#xff08;指定name属性&#xff09;2.1.3 Qualifier注解 2.2 面向接口编程2.3 如果没接口咋办呢&#xff1f;2.…

算法基础课-搜索与图论

DFS 题目链接&#xff1a;842. 排列数字 - AcWing题库 思路&#xff1a;写的很好的题解AcWing 842. 排列数字--深度优先遍历代码注释 - AcWing #include<bits/stdc.h>using namespace std; int n; int st[10]; vector<int> a; void dfs(){if(a.size() n){for(in…

python标准数据类型--集合常用方法

在Python中&#xff0c;集合&#xff08;Set&#xff09;是一种无序且不重复的数据结构&#xff0c;它是由一个无序的、不重复的元素组成的。Python中的集合与数学中的集合概念相似&#xff0c;并且支持一系列常用的方法。本篇博客将深入介绍Python集合的常用方法&#xff0c;帮…

c# wpf XmlDataProvider 简单试验

1.概要 2.代码 <Window x:Class"WpfApp2.Window12"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schemas.microsoft.com/expression/blend…

【C++初阶】String在OJ中的使用(一):仅仅反转字母、字符串中的第一个唯一字母、字符串最后一个单词的长度、验证回文串、字符串相加

前言&#xff1a; &#x1f3af;个人博客&#xff1a;Dream_Chaser &#x1f388;博客专栏&#xff1a;C &#x1f4da;本篇内容&#xff1a;仅仅反转字母、字符串中的第一个唯一字母、字符串最后一个单词的长度、验证回文串、字符串相加 目录 917.仅仅反转字母 题目描述&am…

C#操作MySQL从入门到精通(5)——查询数据

前言 在和MySql数据库交互的过程中,查询数据是使用最频繁的操作,本文详细介绍了查询数据的各种操作,包括查询一列数据、 查询两列数据、查询所有列数据、查询不重复的数据、查询指定行数据,绝对是C#操作MySql数据库史上最详细教程,能够帮助小白快速入门以及将这些功能迅速…

【数据结构】考研真题攻克与重点知识点剖析 - 第 3 篇:栈、队列和数组

前言 本文基础知识部分来自于b站&#xff1a;分享笔记的好人儿的思维导图与王道考研课程&#xff0c;感谢大佬的开源精神&#xff0c;习题来自老师划的重点以及考研真题。此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析&#xff0c;本人技术…

阿里云2核2G和2核4G轻量应用服务器优惠价格表,2024年最新报价

阿里云轻量应用服务器2核2G和2核4G配置优惠价格表&#xff0c;轻量2核2G3M带宽61元一年&#xff0c;轻量2核4G4M带宽165元1年&#xff0c;均不限制月流量&#xff0c;阿里云活动链接 aliyunfuwuqi.com/go/aliyun 活动打开如下图&#xff1a; 阿里云轻量应用服务器价格 61元/年…

上位机图像处理和嵌入式模块部署(qmacvisual实时视频)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 前面我们测试和练习的时候&#xff0c;大部分情况下都是利用图像进行测试的&#xff0c;但是实际情况下&#xff0c;或者准确一点说&#xff0c;工…

android 制作登录页

项目需要可以直接copy layout.xml <?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"…

【六 (2)机器学习-EDA探索性数据分析模板】

目录 文章导航一、EDA&#xff1a;二、导入类库三、导入数据四、查看数据类型和缺失情况五、确认目标变量和ID六、查看目标变量分布情况七、特征变量按照数据类型分成定量变量和定性变量八、查看定量变量分布情况九、查看定量变量的离散程度十、查看定量变量与目标变量关系十一…

软考114-上午题-【计算机网络】-路由

一、路由 二、真题 真题1&#xff1a; 真题2&#xff1a; 真题3&#xff1a; 真题4&#xff1a; 真题5&#xff1a; 路由协议实际上是一种在路由器之间交换路由信息的协议。 路由协议让路由器了解整个网络的拓扑结构&#xff0c;包括哪些网络是直接相连的&#xff0c;哪些网络…

vscode的源码插件GitHub Repositories

打铁还需自身硬&#xff0c;需要不断提升自我&#xff0c;提升自我的一种方式就是看源码&#xff0c;站在更高的维度去理解底层原理&#xff0c;以便以后更好的开发和解决问题&#xff0c;由于源码一个动不动就是几个G甚至十几个G&#xff0c;如果一个个源码下载下来&#xff0…

LeetCode刷题之31.下一个排列

文章目录 1. 题目2.分析3.解答3.1 先排序&#xff0c;后交换3.2 先交换&#xff0c;后排序 1. 题目 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如&#xff0c;arr [1,2,3] &#xff0c;以下这些都可以视作 arr 的排列&#xff1a;[1,2,3]、[1,3,2]、[3…

睿考网:注册会计师科目搭配技巧

注册会计师考试共考六门&#xff0c;关于考试科目的具体搭配&#xff0c;考生可以根据自己的学习情况来进行合理搭配&#xff0c;睿考网为大家推荐常见的科目搭配&#xff1a; 报两科&#xff1a; 1. 《会计》《税法》 2. 《会计》《审计》 3. 《财务成本管理》《公司战略与…

如何从数码相机恢复已删除的照片?

“嗨&#xff0c;我删除了索尼数码相机中的所有照片。有什么办法可以让他们回来吗&#xff1f;” ——刘凯 我们经常从数码相机中删除照片。但是&#xff0c;如果我们误删除了一些重要的照片&#xff0c;则很难将其恢复&#xff0c;因为删除的照片可能会绕过回收站或垃圾箱&am…

SQL语句的编写

##创建用户-建表建库 #创建一个用户名为 feng&#xff0c;允许从任何主机 % 连接&#xff0c;并使用密码 sc123456 进行身份验证的用户。 rootTENNIS 16:33 scmysql>create user feng% identified by sc123456; Query OK, 0 rows affected (0.04 sec) #创建一个名为fen…