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

LeetCode Hot 100:二分查找

LeetCode Hot 100:二分查找

35. 搜索插入位置

思路 1:lower_bound

class Solution {
public:int searchInsert(vector<int>& nums, int target) {return lower_bound(nums.begin(), nums.end(), target) - nums.begin();}
};

思路 2:二分查找

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

74. 搜索二维矩阵

思路 1:从左下方开始查找

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = m ? matrix[0].size() : 0;int i = 0, j = n - 1;while (i < m && j >= 0) {if (matrix[i][j] == target)return true;else if (matrix[i][j] > target)j--;elsei++;}return false;}
};

思路 2:从右上方开始查找

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = m ? matrix[0].size() : 0;int i = m - 1, j = 0;while (i >= 0 && j < n) {if (matrix[i][j] == target)return true;else if (matrix[i][j] > target)i--;elsej++;}return false;}
};

思路 3:二分查找

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = m ? matrix[0].size() : 0;int left = 0, right = m * n - 1;while (left <= right) {int mid = left + (right - left) / 2;int x = mid / n, y = mid % n;if (matrix[x][y] == target)return true;else if (matrix[x][y] > target)right = mid - 1;elseleft = mid + 1;}return false;}
};

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

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if (nums.empty())return {-1, -1};int lower =lower_bound(nums.begin(), nums.end(), target) - nums.begin();if (lower == nums.size() || nums[lower] != target)return {-1, -1};int upper =upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;return {lower, upper};}
};

33. 搜索旋转排序数组

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

153. 寻找旋转排序数组中的最小值

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

4. 寻找两个正序数组的中位数

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size();int n = nums2.size();int total = m + n;if (total % 2 == 1)return getKthElement(nums1, nums2, (total + 1) / 2);elsereturn (getKthElement(nums1, nums2, total / 2) +getKthElement(nums1, nums2, total / 2 + 1)) /2.0;}int getKthElement(vector<int>& nums1, vector<int>& nums2, int k) {int m = nums1.size();int n = nums2.size();int index1 = 0, index2 = 0;while (true) {// 边界情况if (index1 == m)return nums2[index2 + k - 1];if (index2 == n)return nums1[index1 + k - 1];if (k == 1)return min(nums1[index1], nums2[index2]);// 正常情况int newIndex1 = min(index1 + k / 2 - 1, m - 1);int newIndex2 = min(index2 + k / 2 - 1, n - 1);int pivot1 = nums1[newIndex1];int pivot2 = nums2[newIndex2];if (pivot1 <= pivot2) {k -= newIndex1 - index1 + 1;index1 = newIndex1 + 1;} else {k -= newIndex2 - index2 + 1;index2 = newIndex2 + 1;}}}
};

相关文章:

LeetCode Hot 100:二分查找

LeetCode Hot 100&#xff1a;二分查找 35. 搜索插入位置 思路 1&#xff1a;lower_bound class Solution { public:int searchInsert(vector<int>& nums, int target) {return lower_bound(nums.begin(), nums.end(), target) - nums.begin();} };思路 2&#xf…...

打包方式-jar和war的区别

1、jar包 JAR包是类的归档文件&#xff0c;与平台无关的文件格式&#xff0c;其实jar包就是java的类进行编译生成的class文件进行打包的压缩包。 JAR以ZIP文件格式为基础&#xff0c;与ZIP不同的是&#xff0c;JAR不仅用于压缩和发布&#xff0c;还用于部署和封装库、组件和插…...

【论文+源码】基于spring boot的垃圾分类网站

创建一个基于Spring Boot的垃圾分类网站涉及多个步骤&#xff0c;包括环境搭建、项目创建、数据库设计、后端服务开发、前端页面设计等。下面我将引导您完成这个过程。 第一步&#xff1a;准备环境 确保您的开发环境中安装了以下工具&#xff1a; Java JDK 8 或更高版本Mav…...

【C++ STL 模板类】pair 键值对

文章目录 【 1. pair 对象的创建 】【 2. pair 对象的赋值 】【 3. pair 对象的比较 】【 4. pair对象成员的互换】 C STL 标准库提供了 pair 类模板&#xff0c;专门用来将 2 个普通元素 first 和 second&#xff08;可以是 C 基本数据类型、结构体、类自定的类型&#xff09;…...

paddleocr使用FastDeploy 部署工具部署 rknn 模型

在 PC 端转换 pdmodel 模型为 rknn 模型和在板端使用百度飞浆开发的 FastDeploy 部署工具部署 rknn 模型 以下内容是在 PC 端系统为 Ubuntu20.04&#xff0c;板端系统为ubuntu20.04 的环境下实现的 描述&#xff1a; 官网地址 rknn_zoo RKNPU2_SDK …...

Apple Vision Pro市场表现分析:IDC最新数据揭示的真相

随着AR/VR技术逐渐成熟并被更多消费者接受,2024年第二季度(Q2)成为这一领域的一个重要转折点。根据国际数据公司(IDC)发布的最新报告,整个AR/VR市场在本季度经历了显著的增长。接下来,我们将深入探讨Apple Vision Pro在这股增长浪潮中的具体表现。 市场背景 2024年Q2,…...

Mybatis-04.入门-JDBC

一.JDBC 二.原始的JDBC程序代码 &#xff08;不做要求&#xff09; Test public void testJdbc() throws Exception {//1. 注册驱动Class.forName("com.mysql.cj.jdbc.Driver");//2. 获取连接对象String url "jdbc:mysql://localhost:3306/mybatis";Str…...

拥抱云开发的未来:腾讯云数据库、云模板与AI智能化的应用场景探索

本文目录&#xff1a; &#x1f4a1;前言&#xff1a;技术的边界在不断延展&#x1f31f;目录&#x1f308;什么是腾讯云云开发&#xff1f;&#x1f4be;云数据库&#xff1a;让数据成为开发的稳固基石&#x1f951;数据&#xff0c;不再只是数据 &#x1f6e0;云模板&#xf…...

新手铲屎官求推荐,噪音低的宠物空气净化器应该用哪款

当初选择养橘猫就是因为我听到有人说橘猫不容易掉毛才养的&#xff0c;谁知道养了之后和传闻中的不一样&#xff0c;真正的让我明白了什么叫“眼见为实”。 主要是猫掉毛就掉毛&#xff0c;只要我能清理的我都会清理&#xff0c;只要能保证养猫的同时还能保持家里卫生干净就行…...

玄机平台-应急响应-webshell查杀

首先xshell连接 然后进入/var/www/html目录中&#xff0c;将文件变成压缩包 cd /var/www/html tar -czvf web.tar.gz ./* 开启一个http.server服务&#xff0c;将文件下载到本地 python3 -m http.server 放在D盾中检测 基本可以确认木马文件就是这四个 /var/www/html/shell.p…...

LeetCode Hot 100:图论

LeetCode Hot 100&#xff1a;图论 200. 岛屿数量 思路 1&#xff1a;深度优先搜索 class Solution { private:const int dx[4] {-1, 0, 1, 0};const int dy[4] {0, 1, 0, -1};public:int numIslands(vector<vector<char>>& grid) {if (grid.empty())retu…...

tracert和ping的区别

1、简介 tracert&#xff08;在 Windows 系统中&#xff09;和 traceroute&#xff08;在 Unix/Linux 系统中&#xff09;以及 ping 都是网络诊断工具&#xff0c;但它们的功能和用途有所不同&#xff1a; ping&#xff1a; 用途&#xff1a;ping 是一个网络工具&…...

回归、分类模型的评估指标

1. 分类模型的评估指标 评估机器学习模型的好坏至关重要&#xff0c;它帮助我们判断模型的性能、稳定性以及在实际问题中的应用效果。不同类型的机器学习任务&#xff08;分类、回归、聚类等&#xff09;有不同的评估指标。以下是详细介绍常见的模型评估指标&#xff0c;尤其针…...

k8s中如何将pod的标准输出日志输出到一个文件

假设容器的启动命令是 grpcserver&#xff0c;我们将通过修改启动命令&#xff0c;将 grpcserver 的标准输出重定向到指定的日志文件 /var/log/app/grpcserver.log&#xff0c;同时保留标准输出以便 Kubernetes 日志系统仍然能够捕获日志。 目标&#xff1a; 将 grpcserver 的…...

软件工程文档规范要点总结

需求分析文档 1.目标用户应该体现为用例图里的执行者&#xff08;执行者要标明是哪一类用户&#xff09; 2.用例模型由功能概述得到&#xff0c;用例顺序图由基本交互过程得到&#xff0c;分析类图由顺序图得到 3.执行者和用例之间的关系&#xff1a;执行、触发、驱动 用例…...

Django 序列化serializers

在Django中&#xff0c;序列化通常指的是将数据库中的模型数据转换为JSON、XML或其他格式的过程。Django提供了内置的序列化工具&#xff0c;可以通过django.core.serializers模块进行序列化操作。 当你使用Django的序列化功能时&#xff0c;可以序列化以下两种对象类型&#…...

混个1024勋章

一眨眼毕业工作已经一年了&#xff0c;偶然进了游戏公司成了一名初级游戏服务器开发。前两天总结的时候&#xff0c;本来以为自己这一年没学到多少东西&#xff0c;但是看看自己的博客其实也有在进步&#xff0c;虽然比不上博客里的众多大佬&#xff0c;但是回头看也算是自己的…...

Java Spring Boot 项目开发示例指南

开发和扩展一个 Java Spring Boot 项目可以分为几个步骤。以下是一个简单的指南&#xff0c;涵盖项目的创建、基本功能的实现、以及扩展的示例。 第一步&#xff1a;创建 Spring Boot 项目 使用 Spring Initializr 创建项目: 访问 Spring Initializr选择项目的配置&#xff08…...

Python学习路线:从新手到专家

引言 Python 是一种高级编程语言&#xff0c;以其简洁清晰的语法而闻名&#xff0c;被广泛应用于Web开发、数据科学、人工智能、自动化脚本等领域。无论你是编程初学者还是有经验的开发者&#xff0c;Python 都是一个值得学习的语言。本文将提供一份详细的Python学习路线图&am…...

R实验——logistic回归、LDA、QDAKNN

数据集介绍&#xff1a; mpg&#xff0c;miles per gallon即油耗&#xff0c;这个数据集来自卡内基梅隆大学维护的StatLib库。1983年美国统计协会博览会使用了该数据集。这个数据集是对StatLib库中提供的数据集稍加修改的版本。根据Ross Quinlan(1993)在预测属性“mpg”中的使…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...