【算法】【数组与矩阵模块】求最长可整合子数组和子数组的长度
目录
- 前言
- 问题介绍
- 解决方案
- 代码编写
- java语言版本
- c语言版本
- c++语言版本
- 思考感悟
- 写在最后
前言
当前所有算法都使用测试用例运行过,但是不保证100%的测试用例,如果存在问题务必联系批评指正~
在此感谢左大神让我对算法有了新的感悟认识!
问题介绍
原问题
可整合数组定义:如果数组排序后,相邻元素之间差值为1的话,则该数组为可整合数组
给定一个数组arr,求arr中最长的可整合子数组。
如:5532643
返回53264,长度为5
解决方案
原问题:
首先有个定律:相邻元素差值为1的话,该数组的最大值和最小值差值+1就应该是数组的长度
根据该定律遍历数组的所有子数组,每一轮检测数组最大值和最小值差值是否是当前数组长度,求出最长长度即可。
代码编写
java语言版本
原问题:
/*** 二轮测试:求代码可整合子数组的最长长度* 可整合数组定义:对数组排序后,数组中每相邻两个数之间的差值为1* @param arr* @return*/public static Record getLILCp1(int[] arr) {if (arr == null || arr.length == 0) {return null;}Record record = new Record();int min;int max;// 用来判重Set<Integer> set = new HashSet<>();// 遍历每一个子数组for (int i = 0; i < arr.length; i++) {// 每一轮需要清空最值min = arr[0];max = arr[0];set.clear();for (int j = i; j < arr.length; j++) {// 子数组为[i...j],先计算最值// 更新当前子数组的最大值或最小值max = Math.max(max, arr[j]);min = Math.min(min, arr[j]);// 计算当前子数组是否是可整合数组if (set.contains(arr[j])) {// 从j开始存在重复的,直接下一轮break;}else if (max - min + 1 == j - i + 1) {// 值域 == 长度if (j - i + 1 > record.len) {record.setLen(j - i + 1);record.setArr(Arrays.copyOfRange(arr, i, j+1));}set.add(arr[j]);}}}return record;}/*** 存储最长子数组长度和对应子数组的实体类*/static class Record {private int len;private int[] arr;public int getLen() {return len;}public void setLen(int len) {this.len = len;}public int[] getArr() {return arr;}public void setArr(int[] arr) {this.arr = arr;}@Overridepublic String toString() {return "Record{" +"len=" + len +", arr=" + Arrays.toString(arr) +'}';}}public static void main(String[] args) {System.out.println(getLILCp1(new int[]{5,5,3,2,6,4,3}));}
c语言版本
正在学习中
c++语言版本
正在学习中
思考感悟
这道题给我两个启发:
首先求符合要求的子数组类型的问题一定能够通过暴力解决
符合要求的子数组可以通过暴力算法遍历每一个子数组,这道题我一开始往最优解上想的时候,根本没有考虑过使用暴力遍历每一个子数组,虽然可能大多数题目都不会这么写,但是不代表所有的题最优解不会遍历所有子数组。
其次长度和最值差值之间的关系需要记牢
相差1可以用长度等于最值差值这个定律在我刚开始接触算法的时候可能没有想到过,但是数组计数算法也有相似的启发,有时候我们可以多想想数组的index和实际的值有时候是否存在微妙的关联是很重要的。
写在最后
方案和代码仅提供学习和思考使用,切勿随意滥用!如有错误和不合理的地方,务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津!
相关文章:
【算法】【数组与矩阵模块】求最长可整合子数组和子数组的长度
目录前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本思考感悟写在最后前言 当前所有算法都使用测试用例运行过,但是不保证100%的测试用例,如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识! 问题介绍 …...
数据结构:循环队列的实现(leetcode622.设计循环队列)
目录 一.循环队列简单介绍 二.用静态数组实现循环队列 1.数组循环队列结构设计 2.数组循环队列的堆区内存申请接口 3.数据出队和入队的接口实现 4.其他操作接口 5.数组循环队列的实现代码总览 三.静态单向循环链表实现循环队列 1.链表循环队列的结构设计 2.创建静…...
[qiankun]实战问题汇总
[qiankun]实战问题汇总ERROR SyntaxError: Cannot use import statement outside a module问题分析解决方案子应用命名问题问题分析解决方案jsonpFunction详细错误信息问题分析解决方案微应用的注册问题Uncaught Error: application cli5-beta6-test-name died in status LOADI…...
Kafka(6):服务端常用参数配置
参数配置:config/server.properties # Licensed to the Apache Software Foundation (ASF) under one or more # contributor license agreements. See the NOTICE file distributed with # this work for additional information regarding copyright ownership.…...
2023爱分析·云原生智能运维中台市场厂商评估报告:秒云(miaoyun.io)
目录 1. 研究范围定义 2. 云原生智能运维中台市场定义 3. 厂商评估:秒云(miaoyun.io) 4. 入选证书 1. 研究范围定义 数字化时代,应用成为企业开展各项业务的落脚点。随着业务的快速发展,应用的功能迭代变得越…...
hadoop容器化部署
1、原容器 java:openjdk-8u111-jre jre路径: /usr/lib/jvm/java-8-openjdk-amd64 /usr/lib/jvm/java-1.8.0-openjdk-amd64 2、安装ssh docker run -it --name hadoop-test java:openjdk-8u111-jre bash apt-get update apt-get install openssh service ssh start …...
【07-JVM面试专题-JVM运行时数据区的虚拟机栈你知道吗?它的基本结构是什么呢?你知道栈帧的结构吗?那你说说动态链接吧?】
JVM运行时数据区的虚拟机栈你知道吗?它的基本结构是什么呢?你知道栈帧的结构吗?那你说说动态链接吧? JVM运行时数据区的虚拟机栈你知道吗?它的基本结构是什么呢?你知道栈帧的结构吗?那你说说动态…...
Java性能优化-GC优化基础
GC优化基础 调整堆大小 如果在FULL GC系统进行了交换,停顿时间会增长几个数量级,OS 如果G1 GC和后台进程处理堆,将会出现等待数据从磁盘复制到主内存时间较长,速度和下降并且并发模式可能失效 linux 关闭交换区 swapoff -a linu…...
【Tomcat】IDEA编译Tomcat源码-手把手教程
一、环境准备Tomcat不同版本之间有一定的兼容性问题~如下图所示:官网地址:https://tomcat.apache.org/whichversion.html下载tomcat9官网上面的源码:这一篇文章主要是带着大家在自己的IDEA跑起来一个Tomcat。使用的版本是Tomcat9.0.55 和 JDK…...
如何弄小程序?公司企业可以这样做小程序
公司企业现在对于小程序的需求已经是刚需了,即使已经有官网的情况下,也会考虑再弄一个小程序来做小程序官网。那么公司企业如何弄小程序呢?下面跟大家说说方法。 流程一、找小程序服务商 由于一些公司企业并不像现在的互联网公司企业那样有…...
【Git】IDEA集合Git和码云
目录 7、IDEA集合Git 7.1 配置Git忽略文件-IDEA特定文件 7.2 定位 Git 程序 7.3 初始化本地库 7.4 添加到暂存区 7.5 提交到本地库 7.6 切换版本 7.7 创建分支 7.8 切换分支 7.9 合并分支 7.10 解决冲突 8、 Idea集成码云 8.1 IDEA 安装码云插件 8.2 分析工程到码…...
[USACO03FALL / HAOI2006] 受欢迎的牛 G(C++,强连通分量)
题目背景 本题测试数据已修复。 题目描述 每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂,每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 AAA 喜欢 BBB,BBB 喜欢 CCC,那么…...
Vue 动态路由接口数据结构化为符合VueRouter的声明结构及菜单导航结构、动态路由懒加载方法
Vue 动态路由接口数据结构化为符合VueRouter的声明结构及菜单导航结构、动态路由懒加载方法 实现目标 项目打包代码实现按需分割路由懒加载按需打包,排除引入子组件的冗余打包(仅处理打包冗余现象,不影响生产部署)解决路由懒加载…...
Python----------字符串
1.转义字符 注:转义字符放在你所想效果字符前 2.原始字符串 print(r"D:\three\two\one\now") ->D:\three\two\one\now注: 在使用原始字符串时,转义字符不再有效,只能当作原始的字符,每个字符都没有特殊…...
日志收集笔记(架构设计、Log4j2项目初始化、Lombok)
1 架构设计 ELK 技术栈架构设计图: 从左往右看, Beats:主要是使用 Filebeat,用于收集日志,将收集后的日志数据发送给 Kafka,充当 Kafka 的生产者Kafka:高性能消息队列,主要起缓冲…...
一文教你玩转 Apache Doris 分区分桶新功能|新版本揭秘
数据分片(Sharding)是分布式数据库分而治之 (Divide And Conquer) 这一设计思想的体现。过去的单机数据库在大数据量下往往面临存储和 IO 的限制,而分布式数据库则通过数据划分的规则,将数据打散分布至不同的机器或节点上…...
数据挖掘,计算机网络、操作系统刷题笔记54
数据挖掘,计算机网络、操作系统刷题笔记54 2022找工作是学历、能力和运气的超强结合体,遇到寒冬,大厂不招人,可能很多算法学生都得去找开发,测开 测开的话,你就得学数据库,sql,orac…...
将数组中的每个元素四舍五入到指定的精度numpy.rint()
【小白从小学Python、C、Java】 【计算机等级考试500强双证书】 【Python-数据分析】 将数组中的每个元素 四舍五入到指定的精度 numpy.rint() 选择题 请问np.rint(a)的输出结果是? import numpy as np anp.array([-1.72,-1.3,0.37,2.4]) print("【显示】a:\n…...
Web安全之服务器端请求伪造(SSRF)类漏洞详解及预防
如何理解服务器端请求伪造(SSRF)类漏洞当服务器向用户提交的未被严格校验的URL发起请求的时候,就有可能会发生服务器端请求伪造(SSRF,即Server-Side Request Forgery)攻击。SSRF是由攻击者构造恶意请求URL&…...
LeetCode:239. 滑动窗口最大值
239. 滑动窗口最大值 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1: 输入:nums [1,3,-…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换
目录 关键点 技术实现1 技术实现2 摘要: 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式(自动驾驶、人工驾驶、远程驾驶、主动安全),并通过实时消息推送更新车…...
