【每日训练】排序子序列

编程日常/2023/11/30 14:10:05

目录

题目链接:

 输入输出描述&&测试用例:

解析:

程序:


题目链接:

排序子序列_牛客笔试题_牛客网 (nowcoder.com)

 输入输出描述&&测试用例:

 

测试用例:

输入:

6
1 2 3 2 2 1

输出:

2

解析:

题目描述:

        将整型数组的连续的数分成若干的连续排序子序列(排序子序列:非递增和非递减排序),问能划分出多少个这样的子序列。

思路:

        首先是连续的,那么我们找此排序子序列的基础上是遍历这个数组。

        那么先明确一个排序子序列:

         明确之后,我们需要在遍历数组的时候划分好两个区域。非递增序列只要满足递减序列的条件就可以进行统计,相对的非递减序列只要满足递增序列的条件就可以进行统计,如果相等就表示非递减非递增,此时跳到下一个值进行比较即可。

        跳到某一个序列区域后(使用ifelse语句),可以声明一个计数器,进行++操作就可以统计有多少个字序列了。但是注意如果要跳出此区域的话需要进行循环(连续的),比如测试用例:

        

        既然是遍历数组就需要注意边界控制。 

程序:

        使用C++程序进行编写,由于是输入n控制数组长度,所以我利用vector作为数组,利用resize一次性确定数组长度(也可以push_back),循环插入时可以利用[]进行操作。此处还涉及一个边界控制:因为遍历数组进行比较来确定区域的时候,是通过当前数和后一个数进行比较,必然用到下标进行访问。当下标超过数组长度就会发生越界访问。为了方便进行控制我们可以在resize的时候多设置一个,存储为0(数据只能是正整数)。因为这样遍历到最后一个元素就会进入非递增序列将最后一个序列进行统一。(也可以实现其他的控制边界方法)

#include <iostream>
#include <vector>
using namespace std;int main()
{int n = 0, count = 0;  // 输入数组长度和计数子序列个数vector<int> v;  // 存放数据的数组cin >> n; v.resize(n + 1);  // 为了方便边界控制,数组长度+1v[n] = 0;  // 最后一个元素置为0for (int i = 0; i < n; i++){cin >> v[i];}int i = 0;  // 开始遍历数组进行统计序列while (i < n){// 非递增区域if (v[i] > v[i+1])  // []中的i + 1就可以发现我们的边界控制的妙处了{count++;  // 序列数+1while (i < n && v[i] >= v[i + 1])  // 序列是一个连续区域,出需要循环遍历此区域完{  // 注意此处的等于,也表示是一个非递增区域哦i++;}// 结束循环,此处要么i == n 或者此处v[i] < v[i+1] 验证此处以及非递减区域了,此时i必须++,要不然将此数就会算入下一个区域,出现错误,主循环进入下一步即可i++;}else if (v[i] < v[i+1])  // 非递减区域,同理{count++;while (i < n && v[i] <= v[i + 1]){i++;}i++;}else{  // 值相等,跳过i++;}}cout << count << endl;  // 统计结束,输出结果return 0;
}

加油加油~

 


https://www.daipet.cn/news/2748.html

相关文章

人力资源从业者如何提升自己的能力?很实用

一名优秀的人力资源从业者除了能树立正确的招聘理念&amp;#xff0c;制定高效的招聘策略与流程&amp;#xff0c;灵活运用面试方法与技巧外&amp;#xff0c;还要有出色的人力资源管理能力。那么如何提高人力资源管理的能力呢&amp;#xff1f; HR自我提升的一些方法和建议 找兴趣点、加强学习…

【Leetcode刷题笔记06】454. 四数相加 II 383. 赎金信 15. 三数之和 18. 四数之和

454. 四数相加 II 题目描述 给你四个整数数组 nums1、nums2、nums3 和 nums4 &amp;#xff0c;数组长度都是 n &amp;#xff0c;请你计算有多少个元组 (i, j, k, l) 能满足&amp;#xff1a; 0 &lt; i, j, k, l &lt; nnums1[i] nums2[j] nums3[k] nums4[l] 0 做题思路 本题可以使用…

设计模式之美总结(重构篇)

title: 设计模式之美总结&amp;#xff08;重构篇&amp;#xff09; date: 2022-10-27 17:31:42 tags: 设计模式 categories:技术书籍及课程 cover: https://cover.png feature: false 文章目录1. 概述1.1 重构的目的&amp;#xff1a;为什么要重构&amp;#xff08;why&amp;#xff09;&amp;#xff1f;1.…

Linux下 gdb 调试打印函数局部变量

以下面代码&amp;#xff0c;来说明一下&amp;#xff0c;打印函数局部变量的操作&amp;#xff0c;代码如下&amp;#xff1a; #include &lt;stdio.h&gt;void fun1(void){int data1 0;printf(&quot;data1: %d\n&quot;, data1);}void fun2(void){int data2 1;fun1();printf(&quot;***…

inveta PLSB 点线面体 示例工程

https://github.com/inveta/demo/blob/main/Resource/demo.md点线面体生成 POI&amp;#xff08;点&amp;#xff09;ps.emitMessage([&quot;spawn-POI&quot;,&quot;location:X0 Y0 Z0&quot;, // cm&quot;icon:\uE998&quot;, // char&quot;title:POI标题&am…

联网智能门锁解锁智慧公租房

近年来&amp;#xff0c;随着物联网技术的发展&amp;#xff0c;愈来愈多的保障房、公租房、网约房、长短租公寓管理者们都在关注如何实现房屋智能管理&amp;#xff0c;面对租户流动性大、管理复杂&amp;#xff0c;房屋空置、闲置、非法转租&amp;#xff0c;以及租户居住体验差等问题&amp;#xff0c;无从…

单独用HTML javascript CSS 写三版99乘法表,我就是班里最靓的仔

☆ 99乘法表&amp;#xff0c;这个从小学就让我们开始产生肌肉记忆的知识点&amp;#xff0c;伴随一生。而一旦开始学习软件开发知识&amp;#xff0c;99乘法表将是一个基础中不可逃避的巩固升级作业。 ☆ 口算背诵相信大家已经滚瓜烂熟了&amp;#xff0c;一一得一&amp;#xff0c;二二得四&amp;#xff…

【万字总结】C++——list的基本使用和模拟实现(建议收藏)

目录 一、list基本介绍 二、list的使用 1、list的初始化方式 2、list的增删查改 push_front和pop_front与push_back和pop_back insert erase 3、list迭代器的使用 正向迭代器 反向迭代器 4、list获取头尾元素 5、list容量操作 6、list的其他操作 sort splice r…

【Linux】超好用的编译工具 —— gcc/g++

文章目录 前言 一、安装gcc/g 二、背景知识 三、gcc如何完成 1.预处理&amp;#xff08;进行宏替换&amp;#xff09; 2.编译&amp;#xff08;生成汇编&amp;#xff09; 3.汇编&amp;#xff08;生成机器可识别代码&amp;#xff09; 4.连接&amp;#xff08;生成可执行文件或库文件&amp;#xff09; 5.记忆选项的小技…

10月业务安全月报 | 美国将奇虎360和知道创宇列入黑名单;丰田泄露30万用户信息;苹果曝严重漏洞

导语&amp;#xff1a;随着数字化的深入普及&amp;#xff0c;业务愈加开放互联。企业的关键数据、用户信息、基础设施、运营过程等均处于边界模糊且日益开放的环境中&amp;#xff0c;涉及利益流和高附加值的业务面临多样的安全隐患&amp;#xff0c;随时可能遭遇损失&amp;#xff0c;进而影响企业运营…