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

【LeetCode】剑指 Offer(5)

目录

写在前面:

题目:

题目的接口:

解题思路1:

代码:

过啦!!!

解题思路2:

代码:

过啦!!!

写在最后:


写在前面:

军训好累......

题目:剑指 Offer 11. 旋转数组的最小数字 - 力扣(Leetcode)

题目的接口:

class Solution {
public:int minArray(vector<int>& numbers) {}
};

解题思路1:

看到这个题目,我第一个想到的就是,

直接遍历数组,然后找出最小之就行,

用O(N)算法暴力解决。

代码:

class Solution {
public:int minArray(vector<int>& numbers) {//将Min初始化成一个很大的数int Min = INT_MAX;//遍历数组for(int i = 0;i<numbers.size();i++){//找出最小值Min = min(Min, numbers[i]);}return Min;}
};

过啦!!!

如果只是这样的话,那这题刷的可没什么质量, 

如果以后面试的时候,面试官问你怎么提高这个算法的效率,你该怎么办?

所以,我决定在写个二分来做这道题,将算法时间优化成O(logN)。

解题思路2:

因为这是原来是一个升序数组,

如果我们将旋转数组中的旋转的第一个值作为旋转点,

而旋转点就是这个数组的最小值,

所以我们直接找旋转点就行。

用二分的思想,设置 l、r 作为左右下标,取中间 mid 为中间下标。

如果numbers[mid] > numbers[r],旋转点一定在右边区间[ m + 1,j ]。

如果numbers[mid] < numbers[r],旋转点一定在左边区间[ l,m ]。

如果numbers[mid] = numbers[r],特殊情况就让 r--。

当 l = r 的时候,返回numbers[l]就是旋转点。

代码:

class Solution {
public:int minArray(vector<int>& numbers) {//左右下标int l = 0;int r = numbers.size() - 1;//二分while(l < r){int mid = (l + r) / 2;if(numbers[mid] > numbers[r]){l = mid + 1;}else if(numbers[mid] < numbers[r]){r = mid;}//特殊情况else{r--;}}return numbers[l];}
};

但其实这种方法也有缺陷,

他的时间复杂度还是O(N),只是优化了大部分的情况,

在遇到特殊情况的时候(也就是numbers[mid] = numbers[r]的时候就会退化成O(N)算法)

只是平均时间复杂度为O(logN)。

过啦!!!

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果喜欢本文的话,欢迎点赞和评论,写下你的见解。

如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。

之后我还会输出更多高质量内容,欢迎收看。

相关文章:

【LeetCode】剑指 Offer(5)

目录 写在前面&#xff1a; 题目&#xff1a; 题目的接口&#xff1a; 解题思路1&#xff1a; 代码&#xff1a; 过啦&#xff01;&#xff01;&#xff01; 解题思路2&#xff1a; 代码&#xff1a; 过啦&#xff01;&#xff01;&#xff01; 写在最后&#xff1a;…...

外包出来,朋友内推我去一家公司,问的实在是太...

外包出来&#xff0c;没想到算法死在另一家厂子&#xff0c;自从加入这家公司&#xff0c;每天都在加班&#xff0c;钱倒是给的不少&#xff0c;所以也就忍了。没想到8月一纸通知&#xff0c;所有人不许加班&#xff0c;薪资直降30%&#xff0c;顿时有吃不起饭的赶脚。 好在有…...

刷题记录:牛客NC54585小魂和他的数列 [线段树卡常,真恶心]

传送门:牛客 题目描述: 一天&#xff0c;小魂正和一个数列玩得不亦乐乎。 小魂的数列一共有n个元素&#xff0c;第i个数为Ai。 他发现&#xff0c;这个数列的一些子序列中的元素是严格递增的。 他想知道&#xff0c;这个数列一共有多少个长度为K的子序列是严格递增的。 请你帮…...

2019蓝桥杯真题旋转 C语言/C++

题目描述 图片旋转是对图片最简单的处理方式之一&#xff0c;在本题中&#xff0c;你需要对图片顺时针旋转 90 度。 我们用一个 nm 的二维数组来表示一个图片&#xff0c;例如下面给出一个 34 的 图片的例子&#xff1a; 1 3 5 7 9 8 7 6 3 5 9 7 这个图片顺时针旋转 90 度…...

<JVM上篇:内存与垃圾回收篇>11 - 垃圾回收相关算法

对象存活判断 在堆里存放着几乎所有的 Java 对象实例&#xff0c;在 GC 执行垃圾回收之前&#xff0c;首先需要区分出内存中哪些是存活对象&#xff0c;哪些是已经死亡的对象。只有被标记为己经死亡的对象&#xff0c;GC 才会在执行垃圾回收时&#xff0c;释放掉其所占用的内存…...

狂飙Linux平台,软件部署大全

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#x1f4e3;&#x1f4e3;&#x1f4e3; 哈喽&#xff01;大家好&#xff0c;我是【IT邦德】&#xff0c;江湖人称jeames007&#xff0c;10余年DBA及大数据工作经验 一位上进心十足的【大数据领域博主】&#xff01;&#x1f61c;&am…...

积分球原理及积分球类型介绍

标题积分球标准型积分球LED积分球均匀光源便携式高亮度积分球均匀光源微光积分球均匀光源积分球均匀光源iSphere高光谱响应光学积分球其他分类积分球 积分球原理:由于球体内整涂有白色漫反射材料的空腔球体&#xff0c;球壁上开有采样口&#xff0c;当待测样品光源进入积分球的…...

Vision Transformer(ViT) 2: 应用及代码讲解

文章目录1. 代码讲解1.1 PatchEmbed类1&#xff09;__init__ 函数2) forward 过程1.2 Attention类1&#xff09;__init__ 函数2&#xff09;forward 过程1.3 MLP类1&#xff09;__init__ 函数2&#xff09;forward函数1.4 Block类1&#xff09;__init__ 函数2&#xff09;forwa…...

高频面试题|JVM虚拟机的体系结构是什么样的?

一. 前言最近有很多小伙伴都在找工作&#xff0c;他们在面试时经常被面试官问到一个问题&#xff1a;请说说JVM虚拟机的体系结构是什么样的?很多小伙伴都能说出堆、栈等相关内容&#xff0c;但面试官紧接着又问&#xff0c;你还知道其他内容吗&#xff1f;这时不少小伙伴就语塞…...

MyBatis-Plus详细讲解(整合spring Boot)

哈喽&#xff0c;大家好&#xff0c;今天带大家了解的是MyBatis-Plus&#xff08;简称 MP&#xff09;&#xff0c;是一个 MyBatis 的增强工具&#xff0c;在 MyBatis 的基础上只做增强不做改变&#xff0c;为简化开发、提高效率而生。首先说一下MyBatis-Plus的愿景是什么&…...

骨传导耳机是不是智商税?骨传导耳机真的不伤耳吗?

很多人对骨传导耳机是具有一定的了解&#xff0c;但是对骨传导耳机还是有一定的刻板印象&#xff0c;那么骨传导耳机到底是不是智商税呢&#xff1f;主要还是要从骨传导耳机传声原理上讨论。 骨传导耳机是属于固体传声的一种方式&#xff0c;通过骨骼传递声音&#xff0c;在使用…...

模拟实现string

目录 1、基本成员变量 2、默认成员函数 构造函数 析构函数 拷贝构造函数(深拷贝) 赋值运算符重载 3、容量与大小相关的函数 size capacity 4、字符串访问相关函数 operator [ ]重载 迭代器 5、增加的相关函数 reserve扩容 resize push_back追加字符 appe…...

自监督表征预训练之掩码图像建模

自监督表征预训练之掩码图像建模 前言 目前&#xff0c;在计算机视觉领域&#xff0c;自监督表征预训练有两个主流方向&#xff0c;分别是对比学习&#xff08;contrastive learning&#xff09;和掩码图像建模&#xff08;masked image modeling&#xff09;。两个方向在近几…...

华为OD机试题 - 磁盘容量(JavaScript)| 代码+思路+重要知识点

最近更新的博客 华为OD机试题 - 字符串加密(JavaScript) 华为OD机试题 - 字母消消乐(JavaScript) 华为OD机试题 - 字母计数(JavaScript) 华为OD机试题 - 整数分解(JavaScript) 华为OD机试题 - 单词反转(JavaScript) 使用说明 参加华为od机试,一定要注意不要完全背…...

ChatGPT:“抢走你工作的不会是 AI ,而是先掌握 AI 能力的人”

&#x1f497;wei_shuo的个人主页 &#x1f4ab;wei_shuo的学习社区 &#x1f310;Hello World &#xff01; ChatGPT&#xff1a;“抢走你工作的不会是 AI &#xff0c;而是先掌握 AI 能力的人” ChatGPT&#xff1a;美国OpenAI 研发的聊天机器人程序&#xff0c;人工智能技术…...

数据结构与算法(Java版) | 线性结构和非线性结构

之前&#xff0c;我们说过&#xff0c;数据结构是算法的基础&#xff0c;因此接下来在这一讲我就要来给大家重点介绍一下数据结构了。 首先&#xff0c;大家需要知道的是&#xff0c;数据结构包括两部分&#xff0c;即线性结构和非线性结构。知道这点之后&#xff0c;接下来我…...

电商数据查询平台:母婴行业妈妈用品全网热销,头部品牌格局初现

以往&#xff0c;奶粉、纸尿裤这类产品基本就代表了整体母婴市场中的消费品。而如今&#xff0c;随着母婴行业的高速发展和消费升级&#xff0c;母婴商品的种类日益丰富&#xff0c;需求也不断深入。 在京东平台&#xff0c;母婴大品类中除了包含婴童相关的食品&#xff08;奶粉…...

STM32模拟SPI协议获取24位模数转换(24bit ADC)芯片AD7791电压采样数据

STM32模拟SPI协议获取24位模数转换&#xff08;24bit ADC&#xff09;芯片AD7791电压采样数据 STM32大部分芯片只有12位的ADC采样性能&#xff0c;如果要实现更高精度的模数转换如24位ADC采样&#xff0c;则需要连接外部ADC实现。AD7791是亚德诺(ADI)半导体一款用于低功耗、24…...

华为OD机试题 - 交换字符(JavaScript)| 代码+思路+重要知识点

最近更新的博客 华为OD机试题 - 字符串加密(JavaScript) 华为OD机试题 - 字母消消乐(JavaScript) 华为OD机试题 - 字母计数(JavaScript) 华为OD机试题 - 整数分解(JavaScript) 华为OD机试题 - 单词反转(JavaScript) 使用说明 参加华为od机试,一定要注意不要完全背…...

最好的工程师像投资者一样思考,而不是建设者

我在大学期间住在图书馆。“我学习的教科书理论越多&#xff0c;我就会成为一名更好的工程师&#xff0c;”我想。然而&#xff0c;当我开始工作时&#xff0c;我注意到业内最优秀的工程师并不一定比应届毕业生了解更多的理论。他们只是带来了不同的心态&#xff0c;即投资者的…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...