LeetCode热题100——二分查找

二分查找

  • 1. 搜索插入位置
  • 2. 搜素二维矩阵
  • 3. 在排序数组中查找第一个和最后一个元素位置

1. 搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

// 题解:
int searchInsert(vector<int>& nums, int target) {if (nums.empty()) {return 0;}int left = 0;int right = nums.size() - 1;while (left < right) {int mid = (left + right) >> 1;if (nums[mid] < target) {left = mid + 1;} else {right = mid;}}return right ;
}

2. 搜素二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵:每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。
在这里插入图片描述

// 题解:按照行和最后一列遍历,对row和col加减
bool searchMatrix(vector<vector<int>>& matrix, int target) {if (matrix.empty()) return false;int rows = matrix.size();if (matrix[0].empty()) return false;int cols = matrix[0].size();int row = 0;int col = cols - 1;while (col < cols && col >= 0 && row < rows && row >= 0) {if (matrix[row][col] < target) row++;else if (matrix[row][col] > target) col--;else return true;}return false;
}

3. 在排序数组中查找第一个和最后一个元素位置

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

// 题解:两次二分法找到左和右
vector<int> searchRange(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;int first_idx = -1;int last_idx = -1;while (left < right) {int mid = (left + right) / 2;if (nums[mid] > target) {right = mid - 1; } else if (nums[mid] < target) {left = mid + 1;} else {first_idx = mid;right = mid - 1;}}left = 0;right = nums.size() - 1;while (left < right) {int mid = (left + right) / 2;if (nums[mid] > target) {right = mid - 1;} else if (nums[mid] < target) {left = mid + 1;} else {last_idx = mid;left = mid + 1;}}return {first_idx, last_idx};
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

一款快速从数据库中提取信息工具

DataMiner 介绍 DataMiner是一款数据库自动抽取工具&#xff0c;用于快速从数据库中提取信息&#xff0c;目前支持 mysql、mssql、oracle、mongodb等数据库&#xff0c;可导出CSV、HTML。 功能 支持对所有数据库数据进行采样&#xff0c;并指定采样数量。 支持对指定数据库…

MIB 6.1810操作系统实验:准备工作(Tools Used in 6.1810)

6.1810 / Fall 2023 实验环境&#xff1a; Ubuntuxv6实验必要的依赖环境能通过make qemu进入系统 $ sudo apt-get update && sudo apt-get upgrade $ sudo apt-get install git build-essential gdb-multiarch qemu-system-misc gcc-riscv64-linux-gnu binutils-ri…

手把手教你搭建属于自己的快递小程序

在数字化时代&#xff0c;小程序已经成为各行各业连接用户、提供服务、创造价值的重要工具。其中&#xff0c;快递寄件小程序因其实用性和广泛的需求&#xff0c;成为很多企业和开发者关注的焦点。本文将详细介绍如何快速创建快递寄件小程序&#xff0c;以及如何利用它实现盈利…

DVWA - 3

文章目录 XSS&#xff08;Dom&#xff09;lowmediumhighimpossible XSS&#xff08;Reflected&#xff09;lowmediumhighimpossible XSS&#xff08;Stored&#xff09;lowmediumhighimpossible XSS&#xff08;Dom&#xff09; XSS 主要基于JavaScript语言进行恶意攻击&#…

创建一个用户test且使用testtab表空间及testtemp临时表空间并授予其权限,密码随意

文章目录 1、连接到数据库2、创建表空间3、创建用户4、授予权限5、测试 1、连接到数据库 sqlplus / as sysdba2、创建表空间 创建testtab表空间 CREATE TABLESPACE testtab DATAFILE /u01/app/oracle/oradata/orcl/testtab.dbf SIZE 50M AUTOEXTEND ON NEXT 5M MAXSIZE …

金融帝国实验室(Capitalism Lab)V10版本即将推出全新公司徽标(2023-11-13)

>〔在即将推出的V10版本中&#xff0c;我们将告别旧的公司徽标&#xff0c;采用全新光鲜亮丽、富有现代气息的设计&#xff0c;与金融帝国实验室&#xff08;Capitalism Lab&#xff09;的沉浸式体验完美互补&#xff01;〕 ————————————— >〔《公司详细信…

基于纵横交叉算法优化概率神经网络PNN的分类预测 - 附代码

基于纵横交叉算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于纵横交叉算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于纵横交叉优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;针对PNN神…

彩虹桥架构演进之路-性能篇

一、前言 一年前的《彩虹桥架构演进之路》侧重探讨了稳定性和功能性两个方向。在过去一年中&#xff0c;尽管业务需求不断增长且流量激增了数倍&#xff0c;彩虹桥仍保持着零故障的一个状态&#xff0c;算是不错的阶段性成果。而这次的架构演进&#xff0c;主要分享一下近期针对…

PyTorch:张量与矩阵

PyTorch 是一个基于 Python 的科学计算包&#xff0c;专门针对深度学习研究&#xff0c;提供了丰富的工具和库。在 PyTorch 中&#xff0c;张量&#xff08;tensor&#xff09;是深度学习的核心数据结构&#xff0c;它可以看作是可以进行自动微分的多维数组。张量不仅可以代表标…

jQuery【jQuery树遍历、jQuery动画(一)、jQuery动画(二)】(四)-全面详解(学习总结---从入门到深化)

目录 jQuery树遍历 jQuery动画(一) jQuery动画(二) jQuery树遍历 1、 .children() 获得子元素&#xff0c;可以传递一个选择器参数 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-…

单脉冲测角-和差比幅法

和差比幅法单脉冲测角 单脉冲测角的类型阵列接收模型和差波束构造方法和差比幅测角仿真 单脉冲测角的类型 传统的单脉冲测向方法主要有3种&#xff0c;分别是半阵法、加权法和和差比幅法。其实这3种方法都需要形成和波束和差波束&#xff0c;只是波束形成的方法不同&#xff0…

109. 有序链表转化为二叉搜索树

题目 题解 分治。 class Solution:def getMedian(self, left: ListNode, right: ListNode) -> ListNode:找到链表的中间节点slow fast leftwhile fast ! right and fast.next ! right:slow slow.nextfast fast.next.nextreturn slowdef buildTree(self, left: ListNod…

基于python+django的美食餐厅点餐订餐网站

运行环境 开发语言&#xff1a;Python python框架&#xff1a;django 软件版本&#xff1a;python3.7 数据库&#xff1a;mysql 5.7 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;PyCharm/vscode 前端框架:vue.js 项目介绍 本论文主要论述了如何使用python语言开发…

【NLP】理解 Llama2:KV 缓存、分组查询注意力、旋转嵌入等

LLaMA 2.0是 Meta AI 的开创性作品&#xff0c;作为首批高性能开源预训练语言模型之一闯入了 AI 场景。值得注意的是&#xff0c;LLaMA-13B 的性能优于巨大的 GPT-3(175B)&#xff0c;尽管其尺寸只是其一小部分。您无疑听说过 LLaMA 令人印象深刻的性能&#xff0c;但您是否想知…

hadoop 大数据环境配置 ssh免密登录 centos配置免密登录 hadoop(四)

1. 找到.ssh文件夹 cd ~ # 在.ssh文件夹下生成 # cd .ssh 2. 生成私钥公钥命令&#xff1a; ssh-keygen -t rsa3. 发送到需要免密机器&#xff1a; # hadoop23 是我做了配置。在host配置得机器ip和名称得映射 ssh-copy-id hadoop23 4. 成功

微服务nacos实战入门

注册中心 在微服务架构中&#xff0c;注册中心是最核心的基础服务之一 主要涉及到三大角色&#xff1a; 服务提供者 ---生产者 服务消费者 服务发现与注册 它们之间的关系大致如下&#xff1a; 1.各个微服务在启动时&#xff0c;将自己的网络地址等信息注册到注册中心&#x…

leetcode:链表的中间结点

1.题目描述 题目链接&#xff1a;876. 链表的中间结点 - 力扣&#xff08;LeetCode&#xff09; 我们先看题目描述&#xff1a; 2.解题思路 我们用画图用快慢指针来解决这个问题 定义一个快指针fast&#xff0c;一个慢指针slow 快指针一次走两个结点&#xff0c;慢指针一次…

ceph 14.2.10 aarch64 非集群内 客户端 挂载块设备

集群上的机器测试 706 ceph pool create block-pool 64 64 707 ceph osd pool create block-pool 64 64 708 ceph osd pool application enable block-pool rbd 709 rbd create vdisk1 --size 4G --pool block-pool --image-format 2 --image-feature layering 7…

你知道如何科学的学习吗?-关于个人成长的思考

背景 最近在翻看自己工作后的笔记&#xff0c;从有道云笔记到印象笔记&#xff0c;到本地笔记&#xff0c;到自己使用github搭建的博客&#xff0c;到语雀笔记&#xff0c;使用了不同的平台工具&#xff1b;零零总总记录了许多学习笔记、个人成长笔记、职业规划等内容。现在看…

4. 【自动驾驶与机器人中的SLAM技术】点云中的拟合问题和K近邻

目录 1.在三维体素中定义 NEARBY14&#xff0c;实现 14 格最近邻的查找。2.推导arg max||Ad||22的解为ATA的最大特征向量或者奇异向量。3. 将本节的最近邻算法与一些常见的近似最近邻算法进行对比&#xff0c;比如nanoflann&#xff0c;给出精度指标和时间效率指标。4. 也欢迎大…