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

【java刷题】排序子序列

这里写目录标题

  • 问题描述
  • 解决思路
  • 实现代码

问题描述

牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为n的整数数组A,他现在有一个任务是把数组A分为若干段排序子序列,牛牛想知道他最少可以把这个数组分为几段排序子序列.
如样例所示,牛牛可以把数组A划分为[1,2,3]和[2,2,1]两个排序子序列,至少需要划分为2个排序子序列,所以输出2

输入描述

输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)
第二行包括n个整数A_i(1 ≤ A_i ≤ 10^9),表示数组A的每个数字。

输出描述

输出一个整数表示牛牛可以将A最少划分为多少段排序子序列


解决思路

  • 题意分析
    题中说是将一个数组分为若干段排序子序列,而排序子序列给的定义是非递增或者非递减排序的。此时,我们需要理解这个非递增和非递减是什么意思,此处举例说明:
    arr1: 1 2 3 4 5 非递减序列
    arr2: 5 4 3 2 1 非递增序列
    arr3: 1 3 3 3 4非递减序列
    arr4: 5 4 4 3 1 非递增序列
    从这四个例子可以看出,
    非递增序列的意思就是后面的数只能小于或者等于前面的数,即arr[i+1] <= arr[i]
    非递减序列的意思就是后面的数只能大于或等于前面的数,即arr[i+1] >= arr[i]
  • 大致思路
    要将一个数组划分为非递增或者非递减的子序列,就是要遍历整个数组,在遍历过程中,再逐个遍历非递增子序列和非递减子序列,每遍历完一个子序列,计数器就加一,直到整个数组遍历完毕。
  • 具体实现
    题中输入是要输入的数组长度和数组元素,输出是能划分的子序列的个数。
    首先定义一个变量count用来表示子序列的个数,接下来循环遍历数组,比较数组中的前一个数和后一个数,即比较arr[i] 和arr[i+1] ,若arr[i+1] > arr[i],则进入非递减子序列,继续循环遍历,当 arr[i+1] > arr[i]的条件不满足时,即表示当前子序列遍历结束,此时给count++,反之,同理。当arr[i+1] == arr[i]时,此时直接i++,因为两个数相等既可以是非递增序列,也可以是非递减序列,直接将其算入下一个子序列中即可。

实现代码

public class Test {public static void main(String[] args) {yaoqqiuScanner in = new Scanner(System.in);while (in.hasNextInt()){int a = in.nextInt();int[] array = new int[a+1];//多给数组一个长度,避免遍历不到最后一个元素for(int i = 0;i<a;i++){array[i] = in.nextInt();}int i = 0;int count = 0;while(i < a ) {if(array[i] < array[i+1]) {//此时进入非递减子序列(即后面的数均大于或等于前面的数)while (i < a && array[i] <= array[i+1]) {i++;}count++;i++;} else if(i < a  && array[i+1] == array[i]){//相等既可以是非递增也可以是非递减,所以可以不处理,直接加一i++;} else {//进入非递增子序列(即后面的数均小于或等于前面的数)while(i < a && array[i] >= array[i+1]){i++;}count++;i++;}}System.out.println(count);}}
}

相关文章:

【java刷题】排序子序列

这里写目录标题问题描述解决思路实现代码问题描述 牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为n的整数数组A,他现在有一个任务是把数组A分为若干段排序子序列,牛牛想知道他最少可以把这个数组分为几段排序子序…...

Springboot怎么快速集成Mybatis和thymeleaf?

前言有时候做方案&#xff0c;需要模拟一些业务上的一些场景来验证方案的可行性&#xff0c;基本上每次都是到处百度如何集成springbootmybatisthymeleaf这些东西的集成平时基本上一年也用不了一次&#xff0c;虽然比较简单&#xff0c;奈何我真得记不住详细的每一步&#xff0…...

shell常见面试题一

&#xff08;1&#xff09;、set //查看系统变量 &#xff08;2&#xff09;、chsh -s /bin/zsh test //修改用户登录shell &#xff08;3&#xff09;、2>&1 //标准错误重定向到标准输出 &> //同样可以将标准错误重定向到标准输出 如下&#xff1a; ls test.…...

python如何快速采集美~女视频?无反爬

人生苦短 我用python~ 这次康康能给大家整点好看的不~ 环境使用: Python 3.8 Pycharm mou歌浏览器 mou歌驱动 —> 驱动版本要和浏览器版本最相近 <大版本一样, 小版本最相近> 模块使用: requests >>> pip install requests selenium >>> pip …...

kali内置超好用的代理工具proxychains

作者&#xff1a;Eason_LYC 悲观者预言失败&#xff0c;十言九中。 乐观者创造奇迹&#xff0c;一次即可。 一个人的价值&#xff0c;在于他所拥有的。所以可以不学无术&#xff0c;但不能一无所有&#xff01; 技术领域&#xff1a;WEB安全、网络攻防 关注WEB安全、网络攻防。…...

Java栈和队列·下

Java栈和队列下2. 队列(Queue)2.1 概念2.2 实现2.3 相似方法的区别2.4 循环队列3. 双端队列 (Deque)3.1 概念4.java中的栈和队列5. 栈和队列面试题大家好&#xff0c;我是晓星航。今天为大家带来的是 Java栈和队列下 的讲解&#xff01;&#x1f600; 继上一个讲完的栈后&…...

b01lers CTF web 复现

warmup 按照提示依次 base64 加密后访问&#xff0c;可以访问 ./flag.txt&#xff0c;也就是 Li9mbGFnLnR4dA 。 from base64 import b64decode import flaskapp flask.Flask(__name__)app.route(/<name>) def index2(name):name b64decode(name)if (validate(name))…...

三月份跳槽了,历经字节测开岗4轮面试,不出意外,被刷了...

大多数情况下&#xff0c;测试员的个人技能成长速度&#xff0c;远远大于公司规模或业务的成长速度。所以&#xff0c;跳槽成为了这个行业里最常见的一个词汇。 前几天&#xff0c;我看到有朋友留言说&#xff0c;他在面试字节的测试开发工程师的时候&#xff0c;灵魂拷问三小…...

springboot+vue驾校管理系统 idea科目一四预约考试,练车

加大了对从事道路运输经营活动驾驶员的培训管理力度&#xff0c;但在实际的管理过程中&#xff0c;仍然存在以下问题&#xff1a;(1)管理部门内部人员在实际管理过程中存在人情管理&#xff0c;不进行培训、考试直接进行发证。(2)从业驾驶员培训机构不能严格执行管理部门的大纲…...

【pytorch】使用deepsort算法进行目标跟踪,原理+pytorch实现

目录deepsort流程一、匈牙利算法二、卡尔曼滤波车速预测例子动态模型的概念卡尔曼滤波在deepsort中的动态模型三、预测值及测量值的含义deepsort在pytorch中的运行deepsort流程 DeepSORT是一种常用的目标跟踪算法&#xff0c;它结合了深度学习和传统的目标跟踪方法。DeepSORT的…...

Python 基础教程【3】:字符串、列表、元组

本文已收录于专栏&#x1f33b;《Python 基础》文章目录&#x1f315;1、字符串&#x1f95d;1.1 字符串基本操作&#x1f34a;1.1.1 字符串创建&#x1f34a;1.1.2 字符串元素读取&#x1f34a;1.1.3 字符串分片&#x1f34a;1.1.4 连接和重复&#x1f34a;1.1.5 关系运算&…...

(数据结构)八大排序算法

目录一、常见排序算法二、实现1. 直接插入排序2.&#x1f31f;希尔排序3. 选择排序4.&#x1f31f;堆排序5. 冒泡排序7. &#x1f31f;快速排序7.1 其他版本的快排7.2 优化7.3 ⭐非递归7. &#x1f31f;归并排序7.1 ⭐非递归8. 计数排序三、总结1. 分析排序 (Sorting) 是计算机…...

构建GRE隧道打通不同云商的云主机内网

文章目录1. 环境介绍2 GRE隧道搭建2.1 华为云 GRE 隧道安装2.2 阿里云 GRE 隧道安装3. 设置安全组4. 验证GRE隧道4.1 在华为云上 ping 阿里云云主机内网IP4.2 在阿里云上 ping 华为云云主机内网IP5. 总结1. 环境介绍 华为云上有三台云主机&#xff0c;内网 CIDR 是 192.168.0.0…...

48天C++笔试强训 001

作者&#xff1a;小萌新 专栏&#xff1a;笔试强训 作者简介&#xff1a;大二学生 希望能和大家一起进步&#xff01; 本篇博客简介&#xff1a;讲解48天笔试强训第一天的题目 笔试强训 day1选择题12345678910编程题12选择题 1 以下for循环的执行次数是&#xff08;&#xff…...

Android 11新增系统服务

1.编写.aidl文件存放位置&#xff1a;frameworks/base/core/java/android/ospackage android.os;interface ISystemVoiceServer {void setHeightVoice(int flag);void setBassVoice(int flag);void setReverbVoice(int flag);}2.将.aidl文件添加到frameworks/base/Android.bp f…...

“你要多弄弄算法”

开始瞎掰 ▽ 2月的第一天&#xff0c;猎头Luna给我推荐了字节的机会&#xff0c;菜鸡我呀&#xff0c;还是有自知之明的&#xff0c;赶忙婉拒&#xff1a;能力有限&#xff0c;抱歉抱歉。 根据我为数不多的和猎头交流的经验&#xff0c;一般猎头都会稍微客套一下&#xff1a…...

【数据结构】千字深入浅出讲解队列(附原码 | 超详解)

&#x1f680;write in front&#x1f680; &#x1f4dd;个人主页&#xff1a;认真写博客的夏目浅石. &#x1f381;欢迎各位→点赞&#x1f44d; 收藏⭐️ 留言&#x1f4dd; &#x1f4e3;系列专栏&#xff1a;C语言实现数据结构 &#x1f4ac;总结&#xff1a;希望你看完…...

vue面试题(day04)

vue面试题vue插槽&#xff1f;vue3中如何获取refs&#xff0c;dom对象的方式&#xff1f;vue3中生命周期的和vue2中的区别&#xff1f;说说vue中的diff算法&#xff1f;说说 Vue 中 CSS scoped 的原理&#xff1f;vue3中怎么设置全局变量&#xff1f;Vue中给对象添加新属性时&a…...

自动标注工具 Autolabelimg

原理简介~~ 对于数据量较大的数据集&#xff0c;先对其中一部分图片打标签&#xff0c;Autolabelimg利用已标注好的图片进行训练&#xff0c;并利用训练得到的权重对其余数据进行自动标注&#xff0c;然后保存为xml文件。 一、下载yolov5v6.1 https://github.com/ultralytic…...

2023-03-20干活

transformer复现 from torch.utils.data import Dataset,DataLoader import numpy as np import torch import torch.nn as nn import os import time import math from tqdm import tqdmdef get_data(path,numNone):all_text []all_label []with open(path,"r",e…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...