• 每日一题（1）—— 最大连号

    哈喽大家好，我是iecne，本期为大家带来的是博主无意间看到并且遇到的一道超级简单的循环试题，题目不难，但是有点复杂，由于博主无聊，所以将一道无比无比简单的题目写成了一道简单且复杂的题目，解法无语，不喜请评论。不过还是值得学习一下的，有没有朋友有其他的解法，欢迎留言啊~

    目录

    一.题目描述

    二.解法说明

    三. 题目分析

    四.逐条分析

    头文件

    1.输入

    2.储存连续的数

    3.存储到二维数组

    方案一

    方案二

    此循环总代码

    4.个数统计

    五.完整代码

    六.拓展代码

    七.总结

    一.题目描述

     输入长度为 nn 的一个正整数序列，要求输出序列中最长连号的长度。

     

    连号指在序列中，从小到大的连续自然数。

    输入格式

    第一行，一个整数 nn。

    第二行，nn 个整数 a_iai​，之间用空格隔开。

    输出格式

    一个数，最长连号的个数。

    输入输出样例

    输入 #1

    10
1 5 6 2 3 4 5 6 8 9

    输出 #1

    5

    说明/提示

    数据规模与约定

    对于 100\%100% 的数据，保证 1 \leq n \leq 10^41≤n≤104，1 \leq a_i \leq 10^91≤ai​≤109。

    二.解法说明

    由于那些乱七八糟的

    DP ，递归，栈    解法

    我们不需要理睬，来看看纯暴力解法

    三. 题目分析

    1. 输入完之后，用一个布尔数组储存下来连续的数

    2. 将这个连续的数存储在一个二维的数组里

    3. 将二维数组中各个连串的数字个数统计

    4. 在统计的同时用max函数取最大值

    5. 完美输出

    6. return 0养成好习惯

    四.逐条分析

    头文件

    1. #include
    2. using namespace std;

    iostream，大家最熟悉了吧

    using namespace std;   防止std::带来的无尽麻烦

    1.输入

    首先我们看下定义的变量

    int n, a[1000000];

    由于变量定义在int main()之前，所以只需要用到int 

    输入n，接着再循环输入数组a

    1.     cin >> n;
    2. 	for (int i = 1; i <= n; i++)
    3. 	{
    4. 		cin >> a[i];
    5. 	}

    2.储存连续的数

    首先定义一个bool形式的变量b

    1. bool b[1000000];
    2. //bool b[1000000] = { true };

    并且在我们需要储存的地方全部转化成false

    for (int i = 1; i <= n + 5; i++) b[i] = false;

    以防万一循环到 n + 5

    接着循环判断是否连续的数，用 a[i] + 1 == a[i + 1] 来判断，不需要跳过一些时候，因为我们把b数组重复变成true是不会改变的

    1.     for (int i = 1; i <= n; i++)
    2. 	{
    3. 		if (a[i] + 1 == a[i + 1])
    4. 		{
    5. 			b[i] = true;
    6. 			b[i + 1] = true;
    7. 		}
    8. 	}

    3.存储到二维数组

    定义一个变量j和x  ， 并将他们赋值为0

    int j = 0, x = 0;

    接着再定义一个大的二维

    int c[100][1000];

    因为程序需要，定义一个bool形式的变量k

    bool k = false;

    然后我们从i到n开始循环，接着判断b是否为true

    1.     for (int i = 1; i <= n; i++)
    2. 	{
    3. 		if (b[i] == true)
    4. 		{

    看一下下面的表格，是能通过b==true判断的a数组

    a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]a[10]
    562345689

    (1 5 6 2 3 4 5 6 8 9)

    我们把它们分为三组

    5 6

    2 3 4 5 6

    8 9

    该如何实现呢？ 样例给了我们很好的例子

    a[2]a[3]a[4]a[5]a[6]a[7]a[8]
    5623456

    这俩组刚刚好是连贯的，若我们判断a[2]和a[3]，从而将a[2]存入数组c，这样在样例中是行得通的，但是若把a[4]变成9，那么这个思路将会中断

    所以我们分类讨论：

    1. 刚开始记录前两个

    2. 前两个记录完了，一个一个的记录

    其中就用k来标记是1还是2（false则1，true则2）

    方案一

    1.             if (k == false)
    2. 			{
    3. 				if (a[i] + 1 == a[i + 1])
    4. 				{
    5. 					c[j][x] = a[i];
    6. 					x++;
    7. 					c[j][x] = a[i + 1];
    8. 					x++;
    9. 					k = true;
    10. 				}
    11. 			}

    通过x的变化记录二维数组c的变化，若判断成功则两个一起记录

    方案二

    1.             else if (k == true)
    2. 			{
    3. 				if (a[i] + 1 == a[i + 1])
    4. 				{
    5. 					c[j][x] = a[i+1];
    6. 					x++;
    7. 				}
    8. 				else
    9. 				{
    10. 					x = 0;
    11. 					j++;
    12. 					k = false;
    13. 				}
    14. 			}

    再次分类讨论，若成功则只记录一个

    若不成功则，清楚x的记录，赋值为0，将j相加记录下一个，再将k初始化成为false

    此循环总代码

    在此过程当中，我们记录两个之后就马上变成了true，完美的应对了连续数为2的例子

    1.     int j = 0, x = 0;
    2. 	for (int i = 1; i <= n; i++)
    3. 	{
    4. 		if (b[i] == true)
    5. 		{
    6. 			if (k == false)
    7. 			{
    8. 				if (a[i] + 1 == a[i + 1])
    9. 				{
    10. 					c[j][x] = a[i];
    11. 					x++;
    12. 					c[j][x] = a[i + 1];
    13. 					x++;
    14. 					k = true;
    15. 				}
    16. 			}
    17. 			else if (k == true)
    18. 			{
    19. 				if (a[i] + 1 == a[i + 1])
    20. 				{
    21. 					c[j][x] = a[i+1];
    22. 					x++;
    23. 				}
    24. 				else
    25. 				{
    26. 					x = 0;
    27. 					j++;
    28. 					k = false;
    29. 				}
    30. 				
    31. 			}
    32. 			
    33. 		}
    34. 	}

    4.个数统计

    定义变量，maxx和ans

    int ans=0, maxx=0;

    因为上一步骤已经将c数组完善了，成为了这个

     c[i][0]c[i][1]c[i][2]c[i][3]c[i][4]
    c[0]56   
    c[1]23456
    c[2]89  

     

    接着我们从0开始循环到j，由于最后一次循环的结果没有清零，所以j还是保留着

    for (int jj = 0; jj < j; jj++)

    接着我们从0开始循环，n

    注意这里有个测试点，若n=5

    数组a输入 1 1 1 1 1

    则之前的功劳全部作废（我们之前的最小连号是从2开始的）

    所以我们这一次循环便不能按照规矩的循环，我们从1开始，直接跳过c[jj][0]

    这样子，一般情况下所有的数值都小一，但是还可以正常的比较最大值

    其中直接暴力判断这是不是一个大于零的数字

    1.         for (int xx = 1; xx <= n; xx++)
    2. 		{
    3. 			if (c[jj][xx] > 0 && c[jj][xx] <= 100000)
    4. 			{
    5. 				maxx++;
    6. 			}
    7. 		}

    在大循环之中，每次循环之后对比，清零

    1.         ans = max(ans, maxx);
    2. 		maxx = 0;

    以样例的结果如下：

     

     01234结果
    056   1
    1234564
    289   1

    1 4 1 ，max比较的结果储存到ans里，那ans则是4

    我们再看都是1的测试点，若他一个连续的数都没有，则ans=0

    最后一步结尾，输出ans+1

    这样测试点都是1的情况就完美解决

    1. 	int ans=0, maxx=0;
    2. 	for (int jj = 0; jj < j; jj++)
    3. 	{
    4. 		for (int xx = 1; xx <= n; xx++)
    5. 		{
    6. 			if (c[jj][xx] > 0 && c[jj][xx] <= 100000)
    7. 			{
    8. 				maxx++;
    9. 			}
    10. 		}
    11. 		ans = max(ans, maxx);
    12. 		maxx = 0;
    13. 	}
    14. 	cout << ans + 1 << endl;


    五.完整代码

    1. #include
    2. using namespace std;
    3. int n, a[1000000];
    4. bool b[1000000] = { true };
    5. int c[100][1000];
    6. bool k = false;
    7. int main()
    8. {
    9. 	cin >> n;
    10. 	for (int i = 1; i <= n; i++)
    11. 	{
    12. 		cin >> a[i];
    13. 	}
    14. 	for (int i = 1; i <= n + 5; i++) b[i] = false;
    15. 	for (int i = 1; i <= n; i++)
    16. 	{
    17. 		if (a[i] + 1 == a[i + 1])
    18. 		{
    19. 			b[i] = true;
    20. 			b[i + 1] = true;
    21. 		}
    22. 	}
    23. 	int j = 0, x = 0;
    24. 	for (int i = 1; i <= n; i++)
    25. 	{
    26. 		if (b[i] == true)
    27. 		{
    28. 			if (k == false)
    29. 			{
    30. 				if (a[i] + 1 == a[i + 1])
    31. 				{
    32. 					c[j][x] = a[i];
    33. 					x++;
    34. 					c[j][x] = a[i + 1];
    35. 					x++;
    36. 					k = true;
    37. 				}
    38. 			}
    39. 			else if (k == true)
    40. 			{
    41. 				if (a[i] + 1 == a[i + 1])
    42. 				{
    43. 					c[j][x] = a[i+1];
    44. 					x++;
    45. 				}
    46. 				else
    47. 				{
    48. 					x = 0;
    49. 					j++;
    50. 					k = false;
    51. 				}
    52. 				
    53. 			}
    54. 			
    55. 		}
    56. 	}
    57. 	int ans=0, maxx=0;
    58. 	for (int jj = 0; jj < j; jj++)
    59. 	{
    60. 		for (int xx = 1; xx <= n; xx++)
    61. 		{
    62. 			if (c[jj][xx] > 0 && c[jj][xx] <= 100000)
    63. 			{
    64. 				maxx++;
    65. 			}
    66. 		}
    67. 		ans = max(ans, maxx);
    68. 		maxx = 0;
    69. 	}
    70. 	cout << ans + 1 << endl;
    71. 	return 0;
    72. }
    73.  
    74. /*
    75. 1 5 6 2 3 4 5 6 8 9
    76. 5 6 2 3 4 5 6 8 9
    77. 5 6            2
    78. 2 3 4 5 6      5
    79. 8 9            2
    80. */

    六.拓展代码

    除了作者蒟蒻的代码，还可以用递归

    1. #include
    2. using namespace std;
    3. int n;
    4. int a[10010]={0};
    5. int hs(int i)
    6. {
    7. 	if(i==n-1)
    8. 		return 1;
    9. 	if(a[i]+1==a[i+1])
    10. 		return hs(i+1)+1;
    11. 	else
    12. 		return 1;
    13. }
    14. int main()
    15. {
    16. 	cin>>n;
    17. 	for(int i=0;i
    18. 	{
    19. 		cin>>a[i];
    20. 	}
    21. 	int maxn=0;
    22. 	for(int i=0;i
    23. 	{
    24. 		maxn=max(maxn,hs(i));
    25. 	}
    26. 	cout<
    27. }

    DP代码

    1. #include
    2. using namespace std;
    3. int main()
    4. {
    5. 	int n;
    6. 	cin>>n;
    7. 	int a[n+1],dp[n+1];
    8. 	for(int i=1;i<=n;i++)
    9. 	{
    10. 		cin>>a[i];
    11. 	}
    12. 	int maxn=0;
    13. 	for(int i=n;i>0;i--)
    14. 	{
    15. 		if(i==n)
    16. 		{
    17. 			dp[i]=1;
    18. 		}
    19. 		else
    20. 		{
    21. 			if(a[i+1]-1==a[i])
    22. 			{
    23. 				dp[i]=dp[i+1]+1;
    24. 			}
    25. 			else
    26. 			{
    27. 				dp[i]=1;
    28. 			}
    29. 		}
    30. 		maxn=max(dp[i],maxn);
    31. 	}
    32. 	cout<
    33. 	return 0;
    34. }

    七.总结

    本节课主要是讲解了一维数组二维数组暴力DP以及递归结合与一题的题目，相信大家对这个逻辑有了一定的理解，大家可以自己动手敲敲代码，感受一下，请大家继续关注。

    包教包会，帅的人已然点赞收藏关注，而丑的人还在犹豫，被犹豫了，快三连吧！

     本期收录于博主的专栏——C++每日一题，适用于学习编程者，感兴趣的朋友们可以订阅，看到其他的内容

     C++每日一题_iecne的博客-CSDN博客

    目录就不放辣，点击链接进入吧~

     感谢每一个观看本篇文章的朋友，更多精彩敬请期待：iecne的博客_CSDN博客-C++保姆级入门教程领域博主

    文章存在借鉴，如有侵权请联系修改删除！dd8b4788b2554df4bec4b8202395cad2.gif

     

  • 相关阅读:
    HTML之如何下载网页中的音频(二)
    ansible镜像构建使用
    【Azure Developer - 密钥保管库 】使用 Python Azure SDK 实现从 Azure Key Vault Certificate 中下载证书(PEM文件)
    常用Git命令记录
    云原生应用开发培训，开启云计算时代的新征程
    Python猜拳小游戏 彩色控制台版
    性能测试之稳定性测试和并发压力测试的TPS计算
    C++多线程学习
    const修饰指针
    外包干了2个月，技术退步明显了...
  • 原文地址：https://blog.csdn.net/CSDN_linyanchen/article/details/126101531