每日算法打卡:连号区间数 day 18

这篇具有很好参考价值的文章主要介绍了每日算法打卡:连号区间数 day 18。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

原题链接

1210. 连号区间数

题目难度:简单

题目来源:第四届蓝桥杯省赛C++ B组,第四届蓝桥杯省赛Java B组

题目描述

小明这些天一直在思考这样一个奇怪而有趣的问题:

1 ∼ N 1 \sim N 1N 的某个排列中有多少个连号区间呢?

这里所说的连号区间的定义是:

如果区间 [ L , R ] [L, R] [L,R] 里的所有元素(即此排列的第 L 个到第 R 个元素)递增排序后能得到一个长度为 R − L + 1 R-L+1 RL+1 的“连续”数列,则称这个区间连号区间。

当 N 很小的时候,小明可以很快地算出答案,但是当 NNN 变大的时候,问题就不是那么简单了,现在小明需要你的帮助。

输入格式

第一行是一个正整数 N,表示排列的规模。

第二行是 N 个不同的数字 P i P_i Pi,表示这 N 个数字的某一排列。

输出格式

输出一个整数,表示不同连号区间的数目。

数据范围

1 ≤ N ≤ 10000 1 \le N \le 10000 1N10000,
1 ≤ P i ≤ N 1 \le P_i \le N 1PiN

输入样例1:
4
3 2 4 1 
输出样例1:
7 
输入样例2:
5
3 4 2 5 1 
输出样例2:
9 
样例解释

第一个用例中,有 7 个连号区间分别是: [ 1 , 1 ] , [ 1 , 2 ] , [ 1 , 3 ] [1,1], [1,2], [1,3] [1,1],[1,2],[1,3], [1,4], [2,2], [3,3], [4,4]
第二个用例中,有 9 个连号区间分别是: [ 1 , 1 ] , [ 1 , 2 ] , [ 1 , 3 ] , [ 1 , 4 ] , [ 1 , 5 ] , [ 2 , 2 ] , [ 3 , 3 ] , [ 4 , 4 ] , [ 5 , 5 ] [1,1], [1,2], [1,3], [1,4], [1,5], [2,2], [3,3], [4,4], [5,5] [1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[3,3],[4,4],[5,5]

题目分析

题目的意思就是求1到n的连续子区间的个数,要注意的就是这个排列的顺序是不可改变的,而且每个数字只出现一次

最暴力的做法就是枚举所有的子区间,然后再判断区间是否是连续的,这样的做法大概就是 O ( n 3 log ⁡ n ) O(n^3\log n) O(n3logn)

然后来想一下如何优化,我们首先考虑这个判断的过程是否可以优化,那么一个区间是连号区间有什么样的性质,其实对于一个连号区间,必然是满足最大值减最小值等于子区间左右两个下标相减的,所以这个连号区间的条件就可以等价于最大值与最小值的差是否满足子区间左右下标相减

那么我们如何获取最大值和最小值呢,实际上是可以在第二次循环的过程中就顺便算出来的,因为每一次获取一个新的数据,就可以对已有数据进行比较,取较大或者较小的那个数字即可

这样做的时间复杂度就是 O ( n 2 ) O(n^2) O(n2)文章来源地址https://www.toymoban.com/news/detail-804443.html

示例代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 10010, INF = 1e8;

int n;
int arr[N];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>arr[i];
    
    int ans = 0;
    for(int i=0;i<n;i++) // 枚举区间左端点
    {
        int Min = INF, Max = -INF;
        for(int j=i;j<n;j++)
        {
            Min = min (Min,arr[j]);
            Max = max(Max,arr[j]);
            if(Max-Min==j-i) ans++;
        }
    }
    cout<<ans<<'\n';
    return 0;
}

到了这里,关于每日算法打卡:连号区间数 day 18的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法题打卡day45-背包问题 | 70. 爬楼梯 (进阶)、322. 零钱兑换、279.完全平方数

    70. 爬楼梯 - 力扣(LeetCode) 状态:查看思路后AC。 除了常规的可以爬一或二级台阶,当题目稍微修改一下,变成可以爬m级台阶,之前的DP思路就有局限(dp[i] = dp[i-1] + dp[i-2),为了通杀这类问题,可以将题目转换为完全背包问题,可以爬的楼梯级数就是背包中的物品,楼梯总

    2024年02月11日
    浏览(50)
  • 算法打卡day39|动态规划篇07| Leetcode 70. 爬楼梯(进阶版)、322. 零钱兑换、279.完全平方数

    Leetcode 70. 爬楼梯(进阶版) 题目: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 = m n)个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 输入描述:输入共一行,包含两个正整数,分别表示n, m 输出描述:输出一个整数,

    2024年04月14日
    浏览(65)
  • 面试题30天打卡-day18

    单例是一种设计模式,应用该模式的类只会生成一个实例 ,单例模式保证了在程序的不同位置都可以且仅可以取到同一个对象实例,并提供一个访问它的全局访问点。 单列模式好处: 由于类只有一个实例,因此可以避免在多个地方创建多个实例,从而减少内存使用。 可以提

    2024年02月02日
    浏览(37)
  • 每日打卡day8——差分练习

    输入一个长度为 n 的整数序列。 接下来输入 m 个操作,每个操作包含三个整数 l,r,c,表示将序列中 [l,r] 之间的每个数加上 c。 请你输出进行完所有操作后的序列。 输入格式 第一行包含两个整数 n 和 m。 第二行包含 n 个整数,表示整数序列。 接下来 m 行,每行包含

    2024年02月17日
    浏览(42)
  • 每日打卡day9——差分矩阵

    输入一个 n 行 m 列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y2,c,其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。 每个操作都要将选中的子矩阵中的每个元素的值加上 c。 请你将进行完所有操作后的矩阵输出。 输入格式 第一行包

    2024年02月16日
    浏览(48)
  • 蓝桥杯专题-试题版-【矩阵乘法】【连号区间数】【闰年判断】【时间转换】

    点击跳转专栏=Unity3D特效百例 点击跳转专栏=案例项目实战源码 点击跳转专栏=游戏脚本-辅助自动化 点击跳转专栏=Android控件全解手册 点击跳转专栏=Scratch编程案例 点击跳转=软考全系列 点击跳转=蓝桥系列 专注于 Android/Unity 和各种游戏开发技巧,以及 各种资源分享 (网站、

    2024年02月11日
    浏览(50)
  • English Learning - L3 作业打卡 Lesson3 Day18 2023.5.22 周一

    ⏰打卡时间:2023.05.22 6:00-17:00 训练技巧顺序: 【完全听写法】➡️【车轮法】➡️【影子跟读法】 ⏱【练习时间】60 mins /ˈpiːpl sed maɪ ˈmʌðə wəz ə gʊd eg/ 语音现象描述+自身问题总结: (连读、重读、弱读、浊化、断句、语调等) 人们常夸我妈妈是“好人( a good egg)”

    2024年02月07日
    浏览(41)
  • 算法训练day36|贪心算法 part05(重叠区间三连击:LeetCode435. 无重叠区间763.划分字母区间56. 合并区间)

    题目链接🔥🔥 给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。 示例 1: 输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1 解释: 移除 [1,3] 后,剩下的区

    2024年02月09日
    浏览(61)
  • C++---区间DP---棋盘分割(每日一道算法2023.5.2)

    注意事项: 涉及到\\\"矩阵/二维前缀和\\\"的一些知识,建议先理解那篇文章。 题目: 将一个 8×8 的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的部分继续如此分割,这样割了 (n−1) 次后,连同最后剩下的矩形棋盘共有 n 块矩形棋盘。(每次切

    2024年02月02日
    浏览(32)
  • Day 36 贪心算法 part05 : 435. 无重叠区间 763.划分字母区间 56. 合并区间

    56. 合并区间 以数组  intervals  表示若干个区间的集合,其中单个区间为  intervals[i] = [starti, endi]  。请你合并所有重叠的区间,并返回  一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间  。 示例 1: 示例 2: 提示: 1 = intervals.length = 104 intervals[i].length == 2 0 =

    2024年02月09日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包