当前位置: 首页 > 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;即投资者的…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...

渗透实战PortSwigger靶场:lab13存储型DOM XSS详解

进来是需要留言的&#xff0c;先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码&#xff0c;输入的<>当成字符串处理回显到页面中&#xff0c;看来只是把用户输…...