【题解】旋转数组的最小数字、比较版本号
文章目录
- 旋转数组的最小数字
- 比较版本号
旋转数组的最小数字
题目链接:旋转数组的最小数字
解题思路1:遍历求最小值
代码如下:
int minNumberInRotateArray(vector<int> rotateArray) {int min = rotateArray[0];for(auto const& e: rotateArray){if(e < min){min = e;}}return min;}
解题思路2:比大小,最小的值一定是从数组最大值开始减小的那个值,也就是说第一次不是递增的那个值就是最小值,另一种情况是数组的第一个值,比如[1,2,2,2,2]这种情况
代码如下:
int minNumberInRotateArray(vector<int> rotateArray) {for(int i=0; i<rotateArray.size()-1; ++i){if(rotateArray[i+1] < rotateArray[i])return rotateArray[i+1];}return rotateArray[0];}
解题思路3:二分
我们将旋转的前后部分看作两段,两段分别有序,此时我们可以试一试二分;我们将大问题不断划分为小问题,不断的缩减区间,最终得到最小值所在区间,得到最小值。
我们用双指针指向区间首尾,再求得区间中间值,如果区间中点值大于区间最右侧值,那么说明最小值在[mid,right]之间,如果小于,那么最小值在[left,mid]之间,如果相等,那就逐步缩小范围,一步一步跨过相等的那些值再进行比较
代码如下:
int minNumberInRotateArray(vector<int> rotateArray) {int left = 0;int right = rotateArray.size() - 1;while(left < right){int mid = (left + right) / 2;if(rotateArray[mid] > rotateArray[right]){left = mid + 1;}else if(rotateArray[mid] == rotateArray[right]){right--;}else {right = mid;}}return rotateArray[left];}
比较版本号
题目链接:比较版本号
解题思路:双指针
我们用点来对版本号字符串进行分割,比较这两个版本号,直接使用双指针来进行比较,两个指针分别指向两个字符串进行比较
同时,由于前导零不参与比较,我们不知道数字前面有多少个前导零,所以还是将字符串转化为数字比较更方便
代码如下:
int compare(string version1, string version2) {int n1 = version1.size();int n2 = version2.size();int i = 0;//version1的指针int j = 0;//version2的指针while(i < n1 || j < n2){long long num1 = 0;while(i < n1 && version1[i] != '.'){num1 = num1*10 + (version1[i]-'0');i++;}i++;long long num2 = 0;while(j < n2 && version2[j] != '.'){num2 = num2*10 + (version2[j]-'0');j++;}j++;if(num1 > num2) return 1;if(num1 < num2) return -1;}return 0;}
解题思路2:分割后比较
以点为间隔,将字符串进行分割,分割转化为数字存放进数组,再依次取出数组中的元素进行一一对比,得出结果
代码如下:
//拆分版本号的辅助函数void splitstring(vector<int>& nums, string& version){int n = version.size(), num = 0;for(int i=0; i<n; ++i){if(version[i] == '.'){nums.push_back(num);num = 0;}else{num = num*10 + (version[i]-'0');}}nums.push_back(num);//最后一段数字}int compare(string version1, string version2) {vector<int> nums1, nums2;splitstring(nums1, version1);splitstring(nums2, version2);int n1 = nums1.size();int n2 = nums2.size();int p1 = 0, p2 = 0;for(int i=0; i<max(n1,n2); ++i){p1 = i < n1 ? nums1[i] : 0;p2 = i < n2 ? nums2[i] : 0;if(p1 > p2) return 1;if(p1 < p2) return -1;}return 0;}
相关文章:
【题解】旋转数组的最小数字、比较版本号
文章目录 旋转数组的最小数字比较版本号 旋转数组的最小数字 题目链接:旋转数组的最小数字 解题思路1:遍历求最小值 代码如下: int minNumberInRotateArray(vector<int> rotateArray) {int min rotateArray[0];for(auto const&…...
springboot系统内多级调用报错日志输出顺序
忘记,模糊,故专门验证下 比如方法1调用方法2 方法2又调用方法3 方法3报错 那么报错日志中哪个方法所在行先打印出来? 直接上测试代码 package pers.wwz.study.exception.controller;import lombok.extern.slf4j.Slf4j; import org.springframework.web.bind.annotation.Requ…...
django——配置 settings.py 及相关参数说明
3. 配置 settings.py 及相关参数说明 3.1 配置setting.py文件 设置setting.py文件 加入安装的库 apps.erp_test, rest_framework, django_filters, drf_spectacular,加入新增的APP users启动项目 # 运行项目先执行数据库相关操作,再启动 django 项目 python manag…...
OptaPlanner笔记1
1.1 什么是OptaPlanner 每个组织都面临规划问题:为产品或服务提供有限的受约束的资源(员工、资产、时间和金钱)。OptaPlanner用来优化这种规划,以实现用更少的资源来做更多的业务。 这被称为Constraint Satisfaction Programming…...
github 镜像站及下载加速网址
1、提供常用的镜像网址(记住千万别登录账号): https://github.com.cnpmjs.org https://hub.fastgit.org https://hub.nuaa.cf/ https://hub.yzuu.cf/ https://hub.njuu.cf/上面的网址是一个克隆版的Github,上面的镜像网站内容跟G…...
大数据-玩转数据-Flink RedisSink
一、添加Redis Connector依赖 具体版本根据实际情况确定 <dependency><groupId>org.apache.flink</groupId><artifactId>flink-connector-redis_2.11</artifactId><version>1.1.5</version> </dependency>二、启动redis 参…...
c++病毒/恶搞代码大全( 上 )
注:以下代码应勿用于非法(Dev-c5.11实测可用) 1: 效果:无限生成cmd 解决方法:关闭程序即可 #include<bits/stdc.h> #include<windows.h> using namespace std; int main() {while(1)system("start cmd"…...
【数学建模】清风数模更新5 灰色关联分析
灰色关联分析综述 诸如经济系统、生态系统、社会系统等抽象系统都包含许多因素,系统整体的发展受各个因素共同影响。 为了更好地推动系统发展,我们需要清楚哪些因素是主要的,哪些是次要的,哪些是积极的,哪些是消极的…...
Windows下运行Tomcat服务时报GC Overhead Limit Exceeded
根本原因是在新建Tomcat作为Windows服务时,系统默认设置的堆内存太小了,我们打开/bin/service.bat文件,将如下图所示的默认值改大一些就好了 if "%JvmMs%" "" set JvmMs512 if "%JvmMx%" "" set J…...
OpenCV实例(八)车牌字符识别技术(一)模式识别
车牌字符识别技术(一)模式识别 1.模式识别流程2. 模式识别方式 影响并导致汽车牌照内字符出现缺损、污染、模糊等情况的常见因素有照相机的性能、采集车辆图像时光照的差异、汽车牌照的清洁度等。为了提高汽车牌照字符识别的准确率,本节将把英…...
OPENCV C++(七)霍夫线检测+找出轮廓和外接矩形+改进旋转
霍夫线检测 vector<Vec2f> lines1;HoughLines(canny_mat, lines1, 1, CV_PI / 180.0,90 );//45可以检测里面两条线 80检测出外边两条线 定义存放输出线的向量 此向量输出有<距离,角度> 因为检测的原理就是在变换霍夫空间里面去检测的,这里可…...
Error: EACCES: permission denied, rename ‘/usr/local/lib/node_modules/appium‘
在使用npm uninstall -g appium卸载appium的过程中报错 Error: EACCES: permission denied, rename /usr/local/lib/node_modules/appium -> /usr/local/lib/node_modules/.appium-cfBVovI6 npm ERR! code EACCES npm ERR! syscall rename npm ERR! path /usr/local/lib/n…...
CentOS 7中,配置了Oracle jdk,但是使用java -version验证时,出现的版本是OpenJDK,如何解决?
1.首先,检查已安装的jdk版本 sudo yum list installed | grep java2.移除、卸载圈红的系统自带的openjdk sudo yum remove java-1.7.0-openjdk.x86_64 sudo yum remove java-1.7.0-openjdk-headless.x86_64 sudo yum remove java-1.8.0-openjdk.x86_64 sudo yum r…...
牛客 松鼠回家(二分答案+最短路)
题目描述 松鼠宝宝由于贪玩去了一个具有n个点和m条边的无向图中,现在松鼠宝宝仅有h点体力,所有的边经过一次后会消耗部分体力,同时松鼠爸爸为了惩罚贪玩的松鼠宝宝,每到一个点会扣除部分松果(起点的松果也会扣除&#…...
Mysql in 查询的奇怪方向
Mysql in 查询的奇怪方向 关于表字段存储的数据为 num1,num2,num3时, 还要通过多个num1,num2入参针对该字段进行查询 建表语句 CREATE TABLE test (test_ids varchar(100) DEFAULT NULL COMMENT 保存ids 以逗号分隔 ) ENGINEInnoDB;数据项 查询语句 SELECT test_ids FROM t…...
ORB-SLAM2第二节---双目地图初始化
比起单目初始化,而双目实现地图的初始化非常简单,只需要一帧(左右目图像)即可完成初始化。 行特征点统计。考虑用图像金字塔尺度作为偏移量,在当前点上下正负偏移量(r)内的纵坐标值都认为是匹配点可能存在…...
后端常使用的中间件知识点--持续更新
类型难度mysqlmysql中SQL优化:多角度分析包学包会,sql优化全过程,刨根分析redis多角度剖析redis数据结构及底层实现原理、应用场景MQ简单大体说明RabbitMQ的使用(简单版)mybatis使用JDBC的批量插入百万数据要多少秒一遍…...
非科班的大家如何顺滑转码
近年来,很多人想要从其他行业跳槽转入计算机领域。非计算机科班如何丝滑转码?请来聊聊你的看法和观点,我本身是信息与计算科学专业,周围的同学有不少也是被这个名字“骗过来的”,看这个名字都以为是计算机相关专业&…...
webpack中常见的Loader
目录 1.webpack中的loader是什么?配置方式 2. loader特性3.常见的loader 1.webpack中的loader是什么? loader 用于对模块的"源代码"进行转换,在 import 或"加载"模块时预处理文件 webpack做的事情,仅仅是分…...
RabbitMQ:可靠消息传递的强大消息中间件
消息中间件在现代分布式系统中起着关键作用,它们提供了一种可靠且高效的方法来进行异步通信和解耦。在这篇博客中,我们将重点介绍 RabbitMQ,一个广泛使用的开源消息中间件。我们将深入探讨 RabbitMQ 的特性、工作原理以及如何在应用程序中使用…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...
力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...
