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

二分查找_ x 的平方根搜索插入位置山脉数组的峰顶索引

 x 的平方根 

在0~X中肯定有数的平方大于X,这是肯定的。我们需要从中找出一个数的平方最接近X且不大于X。0~X递增,它们的平方也是递增的,这样我们就可以用二分查找。

我们找出的数的平方是<或者恰好==X,所以把0~X的平方分为<=X >X的两部分,求<=区间的最右端

class Solution {
public:int mySqrt(int x) {long long left=0,right=x;while(left<right){long long mid=left+(right-left+1)/2;if(mid*mid<=x) left=mid;else right=mid-1;}return left;}
};

long long防止超出int范围

搜索插入位置

递增数组,找到相等返回下标,反正按顺序插入(恰好比target大的值),也就是目标值>=target。把区间分为<target >=target,找右区间左端

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left=0,right=nums.size()-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]<target) left=mid+1;else right=mid;}if(nums[left]<target) left++;//left恰好是数组最后一个元素return left;}
};

山脉数组的峰顶索引

这段数组可以分成两部分,前一部分递增 后一部分递减。

这样我们就可以用二分查找,如果mid处于递增位置,那么目标值肯定在右边。反之,左边。

下面有两种做法,不同点在于把峰值看做是递增数组上还是递减数组上,在递增数组就是求右端点,在递减数组就是求左端点。

峰值属于递减数组,求左端点

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

因为mid可能正好是目标值,不能跟后面的值比较,后面是递增数组的。

峰值属于递增数组,求右端点

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;}
};

寻找峰值

有三中情况一直递增 / 一直递减 \ 既有递增又有递减 /\/\/\/\

但无论那种情况,如果是递增那它的右边一定有峰值,如果递减它的左边一定有峰值。

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

把峰值看作递增的部分,如果nums[mid]>nums[mid-1]说明递增,那么mid可能是峰值,所以left不能=mid+1,left=mid,让right从右边找过来。

相关文章:

二分查找_ x 的平方根搜索插入位置山脉数组的峰顶索引

x 的平方根 在0~X中肯定有数的平方大于X&#xff0c;这是肯定的。我们需要从中找出一个数的平方最接近X且不大于X。0~X递增&#xff0c;它们的平方也是递增的&#xff0c;这样我们就可以用二分查找。 我们找出的数的平方是<或者恰好X&#xff0c;所以把0~X的平方分为<X …...

汽车建模用什么软件最好?汽车建模渲染建议!

在汽车建模和渲染领域&#xff0c;选择合适的软件对于实现精确的设计与高质量的视觉效果至关重要。那么不少的汽车设计师如何选择合适的建模软件与渲染方案呢&#xff0c;一起来简单看看吧&#xff01; 一、汽车建模用软件推荐 1、Alias Autodesk旗下的Alias系列软件是汽车设…...

蘑菇分类识别数据集(猫脸码客 第222期)

蘑菇分类识别文本/图像数据集 蘑菇&#xff0c;作为一种广泛分布于全球的真菌&#xff0c;隶属于伞菌目伞菌亚门蘑菇科蘑菇属&#xff0c;拥有众多别名&#xff0c;如白蘑菇、洋蘑菇等。其不仅是世界上人工栽培最广泛、产量最高、消费量最大的食用菌品种之一&#xff0c;还在许…...

长短期记忆网络(Long Short-Term Memory,LSTM)

简介&#xff1a;个人学习分享&#xff0c;如有错误&#xff0c;欢迎批评指正。 长短期记忆网络&#xff08;Long Short-Term Memory&#xff0c;简称LSTM&#xff09;是一种特殊的循环神经网络&#xff08;Recurrent Neural Network&#xff0c;简称RNN&#xff09;架构&#…...

WHAT - 引入第三方组件或项目使用需要注意什么

目录 1. 功能匹配2. 社区与维护3. 兼容性4. 性能5. 易用性6. 安全性7. 授权和许可证8. 国际化支持9. 依赖性10. 未来维护 在前端开发过程中引入第三方组件或项目时&#xff0c;应该从以下几个方面进行考虑&#xff0c;以确保引入的组件能够有效解决问题并适合长期维护&#xff…...

原生鸿蒙操作系统HarmonyOS NEXT(HarmonyOS 5)正式发布

华为于10月22日19:00举办“原生鸿蒙之夜暨华为全场景新品发布会”。此次发布会推出全新的原生鸿蒙操作系统HarmonyOS NEXT&#xff08;HarmonyOS 5&#xff09;以及nova 13、WATCH Ultimate、MatePad Pro等新品。 据介绍&#xff0c;此前已经发布过的鸿蒙系统&#xff0c;由于系…...

WindTerm配置快捷键Ctrl+C和Ctrl+V

WindTerm配置快捷键CtrlC和CtrlV 平时使用ssh和sftp连接的时候&#xff0c;经常使用windterm&#xff0c; 但是windterm里面找不到相关的快捷键设置&#xff0c; 因为操作习惯&#xff0c;想把CtrlC和CtrlV分别配置为复制和粘贴&#xff0c;其他的快捷键操作可以按照该方法进…...

AOP学习

corol调用serverce不在是直接调用的是调用底层代理对象&#xff0c;由代理对象统一帮我们处理 AOP常见概念 通知类型 切面顺序...

【ubuntu18.04】ubuntu18.04升级cmake-3.29.8及还原系统自带cmake操作说明

参考链接 cmake升级、更新&#xff08;ubuntu18.04&#xff09;-CSDN博客 升级cmake操作说明 下载链接 Download CMake 下载版本 下载软件包 cmake-3.30.3-linux-x86_64.tar.gz 拷贝软件包到虚拟机 cp /var/run/vmblock-fuse/blockdir/jrY8KS/cmake-3.29.8-linux-x86_64…...

利用Docker搭建一套Mycat2+MySQL8一主一从、读写分离的最简单集群(保姆教程)

文章目录 1、Mycat介绍1.1、mycat简介1.2、mycat重要概念1.3、Mycat1.x与Mycat2功能对比1.2、主从复制原理 2、前提准备3、集群规划4、安装和配置mysql主从复制4.1、master节点安装mysql8容器4.2、slave节点安装mysql8容器4.2、配置主从复制4.3、测试主从复制配置 5、安装mycat…...

算法——python实现堆排序

文章目录 堆排序二叉树堆堆排序的过程&#xff1a;代码实现python中的heapq模块 堆排序 二叉树 关于二叉树的操作&#xff0c;其实核心就是 父节点找子节点&#xff0c;子节点找父节点 如果要将二叉树存储到队列中&#xff0c;就需要找出 父子节点之间的规律&#xff1a; 父…...

uniapp-components(封装组件)

<myitem></myitem> 在其他类里面这样调用。...

avue-crud组件,输入框回车搜索问题

crud组件&#xff0c;输入框回车搜索问题。 文档是并没有标注&#xff0c;实际上已经具备此功能。 需要在curd的option增加属性 searchEnter: true 即可实现输入内容后回车搜索。 avue的一些踩坑记录 - 前端小小菜 - 博客园...

STM32F407ZGT6定时器相关测试

结论&#xff1a; 20us以下的IO翻转操作&#xff0c;存在误差输出比较定时器使能与禁用功能正常输入捕获定时器使能与禁用功能正常单通道输出比较、输入捕获均正常多通道输出比较波形无干扰&#xff0c;但仍是存在20us以下的IO翻转操作存在误差多通道输入捕获正常 一、单一通…...

群晖通过 Docker 安装 GitLab

Docker 配置容器步骤都是大同小异的&#xff0c;可以参考&#xff1a; 群晖通过 Docker 安装 Gitea-CSDN博客 1. 在 Docker 文件夹中创建 GitLab&#xff0c;并创建子文件夹 2. 设置权限 3. 打开 Docker 应用&#xff0c;并在注册表搜索 gitlab-ce 4. 选择 gitlab-ce 映像运行…...

1.Node.js环境搭建(windows)

一、环境搭建(windows) 1.1下载并安装 https://nodejs.org/dist/v18.20.4/node-v18.20.4-x64.msi1.2测试和查看版本 #cmd命令 node -v输出&#xff1a; #能正确输出版本号&#xff0c;说明安装成功 v18.20.41.3使用nodejs启动第一个js #hello.js console.log(hello world!…...

链上相遇,节点之间的悸动与牵连

公主请阅 1. 返回倒数第 k 个节点1.1 题目说明1.2 题目分析1.3 解法一代码以及解释1.3 解法二代码以及解释 2.相交链表2.1 题目说明示例 1示例 2示例 3 2.2 题目分析2.3 代码部分2.4 代码分析 1. 返回倒数第 k 个节点 题目传送门 1.1 题目说明 题目名称&#xff1a; 面试题 02…...

一些简单的编程题(Java与C语言)

引言&#xff1a; 这篇文章呢&#xff0c;小编将会举一些简单的编程题用来帮助大家理解一下Java代码&#xff0c;并且与C语言做个对比&#xff0c;不过这篇文章所出现的题目小编不会向随缘解题系列里面那样详细的讲解每一到题&#xff0c;本篇文章的主要目的是帮助小编和读者们…...

java计算机毕设课设—愤怒小鸟游戏(附源码、文章、相关截图、部署视频)

这是什么系统&#xff1f; 资源获取方式再最下方 java计算机毕设课设—愤怒小鸟游戏(附源码、文章、相关截图、部署视频) 基于Java的愤怒小鸟游戏&#xff0c;我们不仅复刻了原版游戏的核心玩法&#xff0c;还增加了一些创新元素。游戏以2D图形界面呈现&#xff0c;玩家需要…...

【ARM】MDK-Flex服务管理软件使用说明

【更多软件使用问题请点击亿道电子官方网站】 1、 文档目标 记录MDK网络版部署工具Imtools.exe 的各个界面中相关配置的功能说明 2、 问题场景 解决客户咨询&#xff0c;该服务管理软件如何使用&#xff0c;为客户使用服务管理软件后期自行维护增加一定指导作用。 3、软硬件环…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...