当前位置: 首页 > news >正文

【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值

【LeetCode刷题】Day 13

  • 题目1:852.山脉数组的峰顶索引
    • 思路分析:
    • 思路1:暴力枚举O(N)
    • 思路2:二分查找O(logN)
  • 题目2:162.寻找峰值
    • 思路分析:
    • 思路1:二分查找O(logN)

在这里插入图片描述

题目1:852.山脉数组的峰顶索引

在这里插入图片描述

思路分析:

暴力枚举的话就是找单调性,越来越大,直到找到,一个数大于后一个数。这个数就是最大值。
就是单调性相关的问题

思路1:暴力枚举O(N)

思路2:二分查找O(logN)

二分查找:二段性:[单调递增(包括峰顶)][单调递减],左区间找右值,右边左不变,-1+1
代码实现:

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int left=0,right=arr.size()-1;while(left<right){int mid =left+(right-left+1)/2;if(arr[mid]>arr[mid-1]) left=mid;else right=mid-1;}return left;}
};

LeetCode链接:852.山脉数组的峰顶索引


题目2:162.寻找峰值

在这里插入图片描述

思路分析:

这题情况还是比较多,递增开始,还是递减开始,递增开始我们需要找后面比较大的值,递减开始,说明第一个值就可以。

思路1:二分查找O(logN)

不管哪种,我们只需要找区间中峰顶的值,反正逻辑是一样的,下降就找前面,增加就找后面,不管中间怎么变,是这个“山峰”跳到另一个“山峰”,反正找到其中一组就可以,随着区间不断缩小,也会集中在一个“山峰”上。

代码实现

class Solution {
public:int findPeakElement(vector<int>& nums) {int right=nums.size()-1,left=0;while(left<right){   int mid = left+(right-left+1)/2;if(nums[mid]>nums[mid-1]) left=mid;else right=mid-1;}return left;}
};

LeetCode链接:162.寻找峰值


相关文章:

【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值

【LeetCode刷题】Day 13 题目1&#xff1a;852.山脉数组的峰顶索引思路分析&#xff1a;思路1&#xff1a;暴力枚举O(N)思路2&#xff1a;二分查找O(logN) 题目2&#xff1a;162.寻找峰值思路分析&#xff1a;思路1&#xff1a;二分查找O(logN) 题目1&#xff1a;852.山脉数组的…...

《Python学习》-- 实操篇一

一、文件操作 1. 1 读取文本文件 # 文件操作模式 # r (默认) - 只读模式。文件必须存在&#xff0c;否则会抛出FileNotFoundError。在这种模式下&#xff0c;你只能读取文件内容&#xff0c;不能写入或追加。 # w - 写入模式。如果文件存在&#xff0c;内容会被清空&#xff…...

C# 集合(二) —— List/Queue类

总目录 C# 语法总目录 集合二 List/Queue 1. List2. Queue 1. List List有ArrayList和LinkedList ArrayList 类似数组&#xff0c;查找快&#xff0c;插入删除慢(相对)LinkedList 类似双向链表&#xff0c;查找慢(相对)&#xff0c;插入删除快 //ArrayList //ArrayList Arr…...

【TB作品】MSP430 G2553 单片机口袋板,读取单片机P1.4电压显示,ADC

功能 读取P1.4电压&#xff0c;显示到口袋板显示屏&#xff0c;电压越高亮灯越多。 部分程序 while (1){ADC10CTL0 | ENC ADC10SC; // Sampling and conversion startLPM0;adcvalue ADC10MEM; //原始数据 0到1023adtest (float) adcvalue / 1024.…...

知乎x-zse-96、x-zse-81

声明 本文章中所有内容仅供学习交流使用&#xff0c;不用于其他任何目的&#xff0c;抓包内容、敏感网址、数据接口等均已做脱敏处理&#xff0c;严禁用于商业用途和非法用途&#xff0c;否则由此产生的一切后果均与作者无关&#xff01;wx a15018601872 本文章未…...

【Linux】Linux工具——yum,vim

1.Linux 软件包管理器——yum Linux安装软件&#xff1a; 源代码安装&#xff08;不建议&#xff09;rpm安装&#xff08;类似Linux安装包&#xff0c;版本可能不兼容&#xff0c;不推荐&#xff0c;容易报错&#xff09;yum安装&#xff08;解决了安装源&#xff0c;安装版本&…...

ES 生命周期管理

一 .概念 ILM定义了四个生命周期阶段&#xff1a;Hot&#xff1a;正在积极地更新和查询索引。Warm&#xff1a;不再更新索引&#xff0c;但仍在查询。cold&#xff1a;不再更新索引&#xff0c;很少查询。信息仍然需要可搜索&#xff0c;但是如果这些查询速度较慢也可以。Dele…...

【JavaScript脚本宇宙】揭秘HTTP请求库:深入理解它们的特性与应用

深度揭秘&#xff1a;六大HTTP请求库的比较与应用 前言 在这篇文章中&#xff0c;我们将探讨六种主要的HTTP请求库。这些库为处理网络请求提供了不同的工具和功能&#xff0c;包括Axios、Fetch API、Request、SuperAgent、Got和Node-fetch。通过本文&#xff0c;你将对每个库…...

【强化学习】DPO(Direct Preference Optimization)算法学习笔记

【强化学习】DPO&#xff08;Direct Preference Optimization&#xff09;算法学习笔记 RLHF与DPO的关系KL散度Bradley-Terry模型DPO算法流程参考文献 RLHF与DPO的关系 DPO&#xff08;Direct Preference Optimization&#xff09;和RLHF&#xff08;Reinforcement Learning f…...

vue3 todolist 简单例子

vue3 简单的TodList 地址&#xff1a; https://gitee.com/cheng_yong_xu/vue3-composition-api-todo-app-my 效果 step-1 初始化项项目 我们不采用vue cli 搭建项目 直接将上图文件夹&#xff0c;复制到vscode编辑器&#xff0c;清空App.vue的内容 安装包 # 安装包 npm…...

Linux项目编程必备武器!

本文目录 一、更换源服务器二、下载man开发手册(一般都自带&#xff0c;没有的话使用下面方法下载) 一、更换源服务器 我们使用apt-get等下载命令下载的软件都是从源服务器上获取的&#xff0c;有些软件包在某个服务器上存在&#xff0c;而另一个服务器不存在。所以我们可以添加…...

AndroidStudio编译很慢问题解决

如果gradle同步、编译下载很慢&#xff0c;可以换一下仓库阿里云镜像 repositories {maven { url https://maven.aliyun.com/repository/google } maven { url https://maven.aliyun.com/repository/jcenter } maven { url https://maven.aliyun.com/repository/public } goog…...

PHAR反序列化

PHAR PHAR&#xff08;PHP Archive&#xff09;文件是一种归档文件格式&#xff0c;phar文件本质上是一种压缩文件&#xff0c;会以序列化的形式存储用户自定义的meta-data。当受影响的文件操作函数调用phar文件时&#xff0c;会自动反序列化meta-data内的内容,这里就是我们反序…...

Rust安装

目录 一、安装1.1 在Windows上安装1.2 在Linux下安装 二、包管理工具三、Hello World3.1 安装IDE3.2 输出Hello World 一、安装 1.1 在Windows上安装 点击页面 安装 Rust - Rust 程序设计语言 (rust-lang.org)&#xff0c;选择"下载RUSTUP-INIT.EXE(64位&#xff09;&qu…...

513.找树左下角的值

给定一个二叉树&#xff0c;在树的最后一行找到最左边的值。 示例 1: 示例 2: 思路&#xff1a; 深度最大的叶子结点一定是最后一行。 优先左边搜索&#xff0c;记录深度最大的叶子节点&#xff0c;此时就是树的最后一行最左边的值 代码&#xff1a; class Solution:def fi…...

docker基础,docker安装mysql,docker安装Nginx,docker安装mq,docker基础命令

核心功能操作镜像 Docker安装mysql docker run -d --name mysql -p 3306:3306 -e TZAsia/Shanghai -e MYSQL_ROOT_PASSWORDlcl15604007179 mysql docker的基本操作 docker rm 容器名称即可 docker ps 查看当前运行的容器 docker rm 干掉当前容器 docker logs 查看容器命令日…...

MyBatis二、搭建 MyBatis

MyBatis二、搭建 MyBatis 开发环境MySQL 不同版本的注意事项驱动程序&#xff08;Driver&#xff09;JDBC URL连接参数MyBatis配置文件版本兼容性常见问题与解决方案示例&#xff08;MySQL 8.x与MyBatis连接&#xff09; 创建 Maven 工程打包方式&#xff1a;Jar引入依赖创建数…...

昵称生成器

package mainimport ("math/rand" )// 随机昵称 形容词 var nicheng_tou []string{"迷你的", "鲜艳的", "飞快的", "真实的", "清新的", "幸福的", "可耐的", "快乐的", "冷…...

mysql仿照find_in_set写了一个replace_in_set函数,英文逗号拼接字符串指定替换

开发中使用mysql5.7版本数据库&#xff0c;对于英文逗号拼接的字符串&#xff0c;想要替换其中指定的字符串&#xff0c;找不到数据库函数支持&#xff0c;自己写了一个&#xff0c;实测好用&#xff01; /*类似find_in_set,按英文逗号拆分字段,找出指定的旧字符串,替换成新字…...

机械设计手册第一册:公差

形位公差的标注&#xff1a; 形位公差框格中&#xff0c;不仅要表达形位公差的特征项目、基准代号和其他符号&#xff0c;还要正确给出公差带的大小、形状等内容。 1.形位公差框格&#xff1a; 形位公差框格由两个框格或多个格框组成&#xff0c;框格中的主要内容从左到右按…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...