算法通过村第三关-数组青铜笔记|单调数组
文章目录
- 前言
- 单调数组问题
- 搜索插入位置:
- 数组合并问题:
- 总结
前言
提示:本份真诚面对自己、坦然无碍面对他人,就是优雅。
数组中的比较经典性问题:
- 单调数组问题
- 数组合并问题
单调数组问题
参考例子:896. 单调数列 - 力扣(LeetCode)


这里先思考一下:数组有序是前提,通过增/减两种状态,可以采用不同的策略。
- 对于所有的 i <= j 使得 a[i] <= a[j] 则说明数组 a 是单调递增的,反之,对所有的 i <= j ,使得所有的a[i] >= a[j],那么数组 a 是单调递增的。
- 所有遍历数组执行判断就可以解决,由于存在两种情况,我们需要两次循环就可以
展示代码🥰
/*** 第一种方法,两次遍历确定,第一次确定是否递增 ,第二次** @param nums* @return*/public static boolean isMonotonic(int[] nums) {return isSorted(nums, true) || isSorted(nums, false);}public static boolean isSorted(int[] nums, boolean increasing) {int n = nums.length;for (int i = 0; i < n - 1; ++i) {if(increasing){ // 增 if (nums[i] > nums[i + 1]) {return false;}}else{if (nums[i] < nums[i + 1]) {return false;}}}return true;}
当然这样写是可以通过测试的,但是显得有点繁琐了😁,需要遍历两次,想一下这里需要怎么优化呢💡
我们关注一下 i 和 i + 1出现的位置 nums[i] > nums[i + 1], 而在另外的一个地方 j 和 j + 1 出现的位置nums[j] < num[j + 1],那是不是说明就是单调的?这样的化我们可以使用两个变量标记一下,代码如下:
/*** 第二种方式,一次遍历确定*如果是递增的就一定不能出现递减的相邻元素,* 如果出现递减的就一定不能出现递增的相邻元素。* @param nums* @return*/public static boolean isMonotonic_2(int[] nums) {boolean des = true, inc = true;int n = nums.length;for (int i = 0; i < n - 1; i++) {if (nums[i] > nums[i + 1]) {inc = false;}if (nums[i] < nums[i + 1]) {des = false;}}return des || inc;}
技巧:两元式结果的特殊处理,|| 运算的运用。
搜索插入位置:
数组单调性,是一个重要的信息,很多时候要将特定的元素插入到有序序列,并且保证插入后的顺序依然有序,比如力扣的 35 题:35. 搜索插入位置 - 力扣(LeetCode)


这个问题让我们将元素位置返回,比较简单,只需要遍历一边数组就可以找到答案。当然想这样的问题,如何快速的寻找目标元素,我们需要有 二分的概念。以后但凡遇到单调序列中查找的情况,脑海中马上想到二分,迅速反应。
题解:
class Solution {public int searchInsert(int[] nums, int target) {int n = nums.length;for(int i = 0; i < n; i++){if(nums[i] >= target){return i;}}// 出现再最后一个return n;}
}
这里贴一下代码提供思考💡( 二分思想)
public static int searchInsert(int[] nums, int target) {// 拿到 数组长度int n = nums.length;// 确定左右int left = 0, right = n - 1, ans = n;while(left <= right){// 思考这里问什么是 小于等于// 确定 中间值int mid = (right - left) / 2 + left;if (nums[mid] >= target){ans = mid;right = mid - 1;}else {left = mid + 1;}}return ans;}
数组合并问题:
数组合并是将两个或者多个有序数组合并成一个新的数组。当然这个问题本事不是很难,但是要写的出彩,确实需要花费一些功夫的,这个问题也是比较经典的问题。
先来看看力扣 88 题,88. 合并两个有序数组 - 力扣(LeetCode)

对于这个问题嘛,简单的思路就是
- 将nums2 添加在nums1 的后面
- 排序
/*** 方法1:先合并再排序实现排序** @param nums1 第一个数组* @param nums1_len 第一个数组的长度* @param nums2 第二个数组,将nums2合并到nums1中* @param nums2_len 第二个数组的长度*/public static void merge1(int[] nums1, int nums1_len, int[] nums2, int nums2_len) {for (int i = 0; i < nums2_len; i++) {nums1[nums1_len + i] = nums2[i];}Arrays.sort(nums1);}
当然这样写太没有技术含量了,面试官也不喜欢。这道题的关键是将nums2合并到nums1 中并且还要保证有序。因为nums1是数组不能强行插入。如果从前面向后面出插入,数组nums1后面的元素会多次移动,代价太高了。此时再借助一个数组就可以解决这个问题 ans,把选好的数组元素放入ans中,最后返回,很好的解决以上为题。
这样的化面试官会接着向下考察:可以优化一下,或者不申请数组。(专业的说法是,空间复杂度O(n),可以采用O(1)的方法实现?
比较好的方式从后向前插入,nums1 和 nums2 的元素是固定的,所以排序后最远位置一定是nums1 和 nums2 中最大的那一个,一次类推,每次找最大的,就可以实现从后向前填了,展示一下代码:
/*** 方法2:两个数组从后向前逐步合并** @param nums1* @param nums1_len* @param nums2* @param nums2_len*/public static void merge2(int[] nums1, int nums1_len, int[] nums2, int nums2_len) {int n = nums1_len + nums2_len - 1;int len_1 = nums1_len - 1, len_2 = nums2_len - 1;while (len_1 >= 0 && len_2 >= 0){if (nums1[len_1] >= nums2[len_2]){nums1[n--] = nums1[len_1--];}else if (nums1[len_1] < nums2[len_2]){nums1[n--] = nums2[len_2--];}}// 有剩余while(len_1 != -1){nums1[n--] = nums1[len_1--];}while(len_2 != -1){ // 为甚是-1nums1[n--] = nums2[len_2--];}}
思考一下这个代码是不是还可以优化一下💡
总结
提示:单调数组是很重要的一块,二分思想的引入。
相关文章:
算法通过村第三关-数组青铜笔记|单调数组
文章目录 前言单调数组问题搜索插入位置:数组合并问题:总结 前言 提示:本份真诚面对自己、坦然无碍面对他人,就是优雅。 数组中的比较经典性问题: 单调数组问题数组合并问题 单调数组问题 参考例子:896. 单调数列…...
Springboot MultipartFile文件上传与下载
yml文件配置是否可以上传及上传附件大小 servlet:multipart:# 允许文件上传enabled: true# 单个文件大小max-file-size: 20MB# 设置总上传的文件大小max-request-size: 50MB /*** param files* param request* Description 上传文件* Throws* Return java.util.List* Date 202…...
js this变量
js this变量 有个比较特殊的箭头函数没有自己的this,而是继承了外部作用域的this...
Ubuntu ip冲突,修改静态IP方法
虚拟机克隆Ubuntu造成的IP地址相同冲突的问题_虚拟机ip冲突怎么解决_昌哥不爱晚睡的博客-CSDN博客...
windows下dll文件的创建详细教程
1、前言 dll文件是啥,就不作过多赘述了。现在直接教大家如何创建与使用dll文件。 本文基于windows系统,使用的编译相关工具为visual studio 2019。 2、创建dll 2.1 创建dll工程 首先打开visual studio,然后选择创建新项目,在搜…...
一些Git Repo
文章目录 Fake-TcpWow Fishing Script模拟券商柜台 Fake-Tcp Fake-Tcp 自己写的一个伪装包测试。 尝试把UDP的包伪装成TCP包,再发送到Internet Wow Fishing Script 魔兽世界钓鱼脚本 自己写的魔兽世界钓鱼脚本,10.0初期钓鱼成功率90%以上。现在关服了…...
【Unity脚本开源】记录鼠标按下的位置和移动的距离来进行物体的旋转,并在鼠标释放后将物体恢复到初始旋转位置
♥️作者:白日参商 🤵♂️个人主页:白日参商主页 ♥️坚持分析平时学习到的项目以及学习到的软件开发知识,和大家一起努力呀!!! 🎈🎈加油! 加油!…...
金蝶软件实现导入Excel数据分录行信息到单据体分录行中
>>>适合KIS云专业版V16.0|KIS云旗舰版V7.0|K/3 WISE 14.0等版本<<< 金蝶软件中实现[导入Excel数据业务分录行]信息到[金蝶单据体分录]中,在采购订单|采购入库单|销售订单|销售出库单等类型单据中,以少量的必要字段在excel表格中按模板填列好,很方便快捷地从…...
C# 11 中的新增功能
本文内容 泛型属性泛型数学支持数值 IntPtr 和 UIntPtr字符串内插中的换行符 显示另外 11 个 C# 11 中增加了以下功能: 原始字符串字面量泛型数学支持泛型属性UTF-8 字符串字面量字符串内插表达式中的换行符列表模式文件本地类型必需的成员自动默认结构常量 str…...
Postman通用接口加密解决方案
前言: 很对小伙伴对于psotman接口加密不知道如何解决,这里给大家出了一个全网最详细的解决方案,希望能帮助到大家 问题 postman内置加密Api,但不支持RSA加解密码。如何用postman进入rsa加解密?postman中request对象…...
java,钉钉小程序免密登录
一、开发者后台统一登录 - 钉钉统一身份认证 登录钉钉开放平台 二、教程介绍 如何实现用户免登。免登是指用户进入应用后,无需输入钉钉用户名和密码,应用程序可自动获取当前用户身份,进而登录系统的流程。 三、准备工作 注册了钉钉管理员…...
基于docker部署的Selenium Grid分布式自动化测试
01、什么是Selenium Grid Selenium Grid是Selenium套件的一部分,它专门用于并行运行多个测试用例在不同的浏览器、操作系统和机器上。 Selenium Grid有两个版本——老版本Grid 1和新版本Grid 2。我们只对新版本做介绍,因为Selenium团队已经逐渐遗弃老版…...
目标和——力扣494
文章目录 题目描述解法:动态规划题目描述 解法:动态规划 nt findTargetSumWays(vector<int>& nums, int target){int sum...
sql 执行的顺序
在执行 SQL 查询时,通常会按照以下顺序进行处理: FROM 子句:指定要查询的表或视图。WHERE 子句:筛选满足特定条件的行。GROUP BY 子句:将结果按照指定的列进行分组。HAVING 子句:筛选满足特定条件的分组。…...
TCP收发信息(C++)
目录 一、介绍 二、收数据 三、发数据 一、介绍 tcp和udp的区别之一,即tcp是有连接的,udp是无连接的,udp收发数据的代码可以独立运行,tcp发数据前必须确保收数据的一方是打开的,否则无法建立连接。 二、收数据 tc…...
windows Socket简单编程实例
服务端 #include <winsock2.h> #include <string.h> #include <stdio.h> #include <stdlib.h>#pragma comment(lib, "Ws2_32.lib")void error_handing(const char* message) {fputs(message, stderr);fputc(\n, stderr);exit(1); } int mai…...
外企开展中国在线业务的三种网络加速方案:含免ICP备案CDN解决方案
中国作为全球除美国外最大的消费市场,是几乎每个国际化企业都想要深入挖掘的市场,但外国企业在中国开展在线业务需要面临一个比较特殊的挑战:互联网防火墙(GFW)。为此所有想要在中国市场有所作为的外企都需要首先解决这…...
室内UWB定位到达角(AOA)测量精度的提高
抽象的 本文表明,用于在视线 (LoS) 中定位标签的干涉定位系统的方位角测量精度可以通过利用脉冲无线电超宽带 (IR-UWB) 信号来提高,并且无需增加频率带宽。该解决方案采用相位相关 (PC) 方法,最初应用于连续波 (CW) 信号,后来适用于超宽带 (UWB) 脉冲信号。将获得的结果与…...
“深入理解JVM:探索Java虚拟机的内部工作原理“
标题:深入理解JVM:探索Java虚拟机的内部工作原理 摘要:本文将深入探索Java虚拟机(JVM)的内部工作原理,包括JVM的架构、类加载、内存管理、垃圾回收机制等方面。通过理解JVM的内部工作原理,我们…...
TC3XX - MCAL知识点(三十一):FlsLoader MCAL配置及代码实战
目录 1、概述 2、MCAL配置 2.1、FlsLoaderGeneral 2.2、FlsLoaderOptionalApi 2.3、FlsLoaderPFlash0ProtConfig 3、测试代码及结果 3.1、测试代码 3.1.1、初始化 3....
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
怎么让Comfyui导出的图像不包含工作流信息,
为了数据安全,让Comfyui导出的图像不包含工作流信息,导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo(推荐) 在 save_images 方法中,删除或注释掉所有与 metadata …...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
