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

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

相关文章:

LeetCode热题100——二分查找

二分查找 1. 搜索插入位置2. 搜素二维矩阵3. 在排序数组中查找第一个和最后一个元素位置 1. 搜索插入位置 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 // 题…...

使用VC++实现分段线性变换,直方图均衡化、锐化处理(使用拉普拉斯算子)

图像锐化1 实验要求 5.1实验目的、要求 实验目的&#xff1a; &#xff08;1&#xff09;掌握图像增强的原理与相关方法。 &#xff08;2&#xff09;能使用VC实现图像增强的一些相关功能。 实验要求&#xff1a; A部分&#xff1a; &#xff08;1&#xff09;对一幅256级灰度…...

react class改hooks写法

类头修改 export default class EditUseTable extends Component 改为 export default function EditUseTable({})参数修改 constructor(props) {super(props)const {dbRecord, type, currentRecord, readOnly, updateTaxAmount} this.props改为&#xff08;主函数的参数&a…...

桂院校园导航 | 云上高校导航 云开发项目 二次开发教程 1.3

Gitee代码仓库&#xff1a;桂院校园导航小程序 GitHub代码仓库&#xff1a;GLU-Campus-Guide 演示视频 中国大学生计算机设计大赛-移动应用与开发-云上高校导航 升级日志 1.3 优化了小程序的数据存储方式&#xff0c;对部分页面进行了调整&#xff0c;调整了功能和代码。 引…...

sscanf提取相应字符到数组

代码如下 #include<stdio.h> #include<string.h>int main(int argc, char const *argv[]) {char buf[128] {0};int m1 0, m2 0;int s1 0, s2 0;char lrc[128] "";sscanf("[02:16.33][04:11.44]我想大声宣布对你恋恋不舍","[%*1d%d…...

本地开发环境和服务器传输数据的几种方法

❤️觉得内容不错的话&#xff0c;欢迎点赞收藏加关注&#x1f60a;&#x1f60a;&#x1f60a;&#xff0c;后续会继续输入更多优质内容❤️ &#x1f449;有问题欢迎大家加关注私戳或者评论&#xff08;包括但不限于NLP算法相关&#xff0c;linux学习相关&#xff0c;读研读博…...

LeetCode之二叉树

发现更多计算机知识&#xff0c;欢迎访问Cr不是铬的个人网站 最近数据结构学到二叉树&#xff0c;就刷了刷力扣&#xff0c;写这篇文章也是辅助记忆。 103二叉树锯齿形遍历 要解出本道题&#xff0c;首先要会层次遍历。层次遍历我们都知道用一个队列去实现就行。但是力扣这里…...

论文学习——THE USTC SYSTEM FOR ADRESS-M CHALLENGE

文章目录 引言正文Abstract模型基本结构模型效果汇总 Introduction介绍跨语言任务的独特性思路启发和变化如何使用预定义好的音频特征如何使用预定义好的语言模型——语言模型中获取韵律信息结果说明 Dataset数据集Mthods方法使用设计好的特征进行AD检测使用的特征分类和训练方…...

第一百七十五回 如何创建放射形状渐变背景

文章目录 1. 概念介绍2. 实现方法3. 代码与效果3.1 示例代码3.2 运行效果 4. 内容总结 我们在 上一章回中介绍了"如何创建扇形渐变背景"相关的内容&#xff0c;本章回中将介绍" 如何创建放射形状渐变背景"。闲话休提&#xff0c;让我们一起Talk Flutter吧…...

vue实现调用手机拍照、录像功能

目录 前言 准备工作 在这个示例中&#xff0c;我们将使用Vue.js框架来实现我们的目标。如果你还不熟悉Vue.js&#xff0c;推荐先学习一下Vue.js的基础知识。 接下来&#xff0c;我们需要创建一个基于Vue.js的项目。你可以使用Vue CLI来创建一个全新的Vue项目&#xff1a;# 安…...

WPF播放视频

在WPF中&#xff0c;你可以使用MediaElement来播放本地视频。下面是一个简单的例子&#xff1a; <Window x:Class"WPFVideoPlayer.MainWindow"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsof…...

交换机如何配置BGP协议

环境&#xff1a; 华为交换机 华三交换机 问题描述&#xff1a; 交换机如何配置BGP协议 解决方案&#xff1a; 华三交换机上配置案例 1.配置BGP协议&#xff0c;可以按照以下步骤进行&#xff1a; 登录交换机&#xff1a;使用SSH、Telnet或控制台等方式登录到华三交换…...

精通Nginx(14)-配置HTTPS

HTTPS是在 HTTP 协议的基础上使用 TLS/SSL 加密,其主要目标是提高数据传输的安全性。从HTTP2.0开始,HTTPS已经是网站的标准协议,很多开放平台非HTTPS不能访问。Nginx为HTTPS提供了强大的支持,且对应用服务器是完全透明的。 目录 SSL/TLS基础 发展历史 TLS握手过程 加密…...

封装一个简单的table组件

子组件 <template> <el-table :data"tableData" :headers"tableHeaders" style"width: 100%"> <el-table-column v-for"header in tableHeaders" :key"header.prop" :label"header.label" :pro…...

Avalonia UI框架介绍

Avalonia UI是一个跨平台的UI框架&#xff0c;它允许开发者使用XAML和C#语言创建可在多个平台上运行的应用程序&#xff0c;包括Windows、Linux、macOS等。Avalonia UI与WPF非常相似&#xff0c;但是它是开源的&#xff0c;并且更加灵活。 下面是一个简单的Avalonia UI应用程序…...

【入门篇】1.3 redis客户端之 jedis 高级使用示例

文章目录 0.前言1. 发布和订阅消息2. 事务操作3. 管道操作4. jedis 支持哨兵模式5. jedis 支持集群模式5. 参考链接 0.前言 Jedis是Redis的Java客户端&#xff0c;它支持所有的Redis原生命令&#xff0c;使用方便&#xff0c;且可以与Java项目无缝集成。 该库的最新版本支持Re…...

使用CXF调用WSDL(二)

简介 本篇文章主要解决了上篇文章中遗留的对象嵌套问题&#xff0c;要想全面解析无限极的对象嵌套需要使用递归去解决 上文链接&#xff1a; 使用CXF调用WSDL&#xff08;一&#xff09; 上文回顾 上文使用了单方法“ call() ”解决了List和基本类型&#xff08;含String&…...

list.toArray

直接去看原文 原文链接:List的toArray()方法_list.toarray-CSDN博客 -------------------------------------------------------------------------------------------------------------------------------- toArray()介绍 toArray()方法是List接口中提供的方法&#xff…...

2013年11月10日 Go生态洞察:Go语言四周年回顾

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…...

Ubuntu上使用SSH连接到CentOS系统

确保CentOS系统上的SSH服务器已安装并正在运行&#xff1a; 在CentOS上&#xff0c;默认情况下&#xff0c;SSH服务器&#xff08;sshd&#xff09;应该已安装并正在运行。如果不确定&#xff0c;可以通过以下方式检查&#xff1a; sudo systemctl status sshd如果未安装&…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...