【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:852.山脉数组的峰顶索引思路分析:思路1:暴力枚举O(N)思路2:二分查找O(logN) 题目2:162.寻找峰值思路分析:思路1:二分查找O(logN) 题目1:852.山脉数组的…...
《Python学习》-- 实操篇一
一、文件操作 1. 1 读取文本文件 # 文件操作模式 # r (默认) - 只读模式。文件必须存在,否则会抛出FileNotFoundError。在这种模式下,你只能读取文件内容,不能写入或追加。 # w - 写入模式。如果文件存在,内容会被清空ÿ…...
C# 集合(二) —— List/Queue类
总目录 C# 语法总目录 集合二 List/Queue 1. List2. Queue 1. List List有ArrayList和LinkedList ArrayList 类似数组,查找快,插入删除慢(相对)LinkedList 类似双向链表,查找慢(相对),插入删除快 //ArrayList //ArrayList Arr…...
【TB作品】MSP430 G2553 单片机口袋板,读取单片机P1.4电压显示,ADC
功能 读取P1.4电压,显示到口袋板显示屏,电压越高亮灯越多。 部分程序 while (1){ADC10CTL0 | ENC ADC10SC; // Sampling and conversion startLPM0;adcvalue ADC10MEM; //原始数据 0到1023adtest (float) adcvalue / 1024.…...
知乎x-zse-96、x-zse-81
声明 本文章中所有内容仅供学习交流使用,不用于其他任何目的,抓包内容、敏感网址、数据接口等均已做脱敏处理,严禁用于商业用途和非法用途,否则由此产生的一切后果均与作者无关!wx a15018601872 本文章未…...
【Linux】Linux工具——yum,vim
1.Linux 软件包管理器——yum Linux安装软件: 源代码安装(不建议)rpm安装(类似Linux安装包,版本可能不兼容,不推荐,容易报错)yum安装(解决了安装源,安装版本&…...
ES 生命周期管理
一 .概念 ILM定义了四个生命周期阶段:Hot:正在积极地更新和查询索引。Warm:不再更新索引,但仍在查询。cold:不再更新索引,很少查询。信息仍然需要可搜索,但是如果这些查询速度较慢也可以。Dele…...
【JavaScript脚本宇宙】揭秘HTTP请求库:深入理解它们的特性与应用
深度揭秘:六大HTTP请求库的比较与应用 前言 在这篇文章中,我们将探讨六种主要的HTTP请求库。这些库为处理网络请求提供了不同的工具和功能,包括Axios、Fetch API、Request、SuperAgent、Got和Node-fetch。通过本文,你将对每个库…...
【强化学习】DPO(Direct Preference Optimization)算法学习笔记
【强化学习】DPO(Direct Preference Optimization)算法学习笔记 RLHF与DPO的关系KL散度Bradley-Terry模型DPO算法流程参考文献 RLHF与DPO的关系 DPO(Direct Preference Optimization)和RLHF(Reinforcement Learning f…...
vue3 todolist 简单例子
vue3 简单的TodList 地址: https://gitee.com/cheng_yong_xu/vue3-composition-api-todo-app-my 效果 step-1 初始化项项目 我们不采用vue cli 搭建项目 直接将上图文件夹,复制到vscode编辑器,清空App.vue的内容 安装包 # 安装包 npm…...
Linux项目编程必备武器!
本文目录 一、更换源服务器二、下载man开发手册(一般都自带,没有的话使用下面方法下载) 一、更换源服务器 我们使用apt-get等下载命令下载的软件都是从源服务器上获取的,有些软件包在某个服务器上存在,而另一个服务器不存在。所以我们可以添加…...
AndroidStudio编译很慢问题解决
如果gradle同步、编译下载很慢,可以换一下仓库阿里云镜像 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(PHP Archive)文件是一种归档文件格式,phar文件本质上是一种压缩文件,会以序列化的形式存储用户自定义的meta-data。当受影响的文件操作函数调用phar文件时,会自动反序列化meta-data内的内容,这里就是我们反序…...
Rust安装
目录 一、安装1.1 在Windows上安装1.2 在Linux下安装 二、包管理工具三、Hello World3.1 安装IDE3.2 输出Hello World 一、安装 1.1 在Windows上安装 点击页面 安装 Rust - Rust 程序设计语言 (rust-lang.org),选择"下载RUSTUP-INIT.EXE(64位)&qu…...
513.找树左下角的值
给定一个二叉树,在树的最后一行找到最左边的值。 示例 1: 示例 2: 思路: 深度最大的叶子结点一定是最后一行。 优先左边搜索,记录深度最大的叶子节点,此时就是树的最后一行最左边的值 代码: 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 不同版本的注意事项驱动程序(Driver)JDBC URL连接参数MyBatis配置文件版本兼容性常见问题与解决方案示例(MySQL 8.x与MyBatis连接) 创建 Maven 工程打包方式:Jar引入依赖创建数…...
昵称生成器
package mainimport ("math/rand" )// 随机昵称 形容词 var nicheng_tou []string{"迷你的", "鲜艳的", "飞快的", "真实的", "清新的", "幸福的", "可耐的", "快乐的", "冷…...
mysql仿照find_in_set写了一个replace_in_set函数,英文逗号拼接字符串指定替换
开发中使用mysql5.7版本数据库,对于英文逗号拼接的字符串,想要替换其中指定的字符串,找不到数据库函数支持,自己写了一个,实测好用! /*类似find_in_set,按英文逗号拆分字段,找出指定的旧字符串,替换成新字…...
机械设计手册第一册:公差
形位公差的标注: 形位公差框格中,不仅要表达形位公差的特征项目、基准代号和其他符号,还要正确给出公差带的大小、形状等内容。 1.形位公差框格: 形位公差框格由两个框格或多个格框组成,框格中的主要内容从左到右按…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)
LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 题目描述解题思路Java代码 题目描述 题目链接:LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...
