欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

7-7 最长连续递增子序列(20 分) 普通STL解出

程序员文章站 2022-06-08 08:11:36
...

这道题我看了一下  决定写。 在写之前网上看到很多高手的题解,深表敬意。

只是我想用STL来完成一下这道题。

7-7 最长连续递增子序列(20 分)

给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长的连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。

输入格式:

输入第1行给出正整数n(≤10​5​​);第2行给出n个整数,其间以空格分隔。

输出格式:

在一行中输出第一次出现的最长连续递增子序列,数字之间用空格分隔,序列结尾不能有多余空格。

输入样例:

15
1 9 2 5 7 3 4 6 8 0 11 15 17 17 10

输出样例:

3 4 6 8

 

这次我要使用一个名叫 双端队列的东西  deque .

 

本次练习 共测试了几个样例

1 . 1 2 3 4 5

2. 5 4 3 2 1

3. 1 2 3 1 2 3 4

4. 5 4 3 2 1 2 3 4 5 6 6 7 8 9 10 9

5. 0

 

我的代码是怎样想出来的??

1.看到题目之后 我想 既然是一个递增子序列 我可以用 双端队列数组存储下这些数列 然后动用带cmp函数的sort排序输出双端队列数组的首地址下的所有元素。 比如题目样例 1 9 2 5 7 3 4 6 8 0 11 15 17 17 10                                                                           可想而知   1 9 存在 [0] ,2 5 7 存在 [1] , 3 4 6 8 存在 [2] , 0 11 15 17存在 [3]  17 存在 [4]  10 存在 [5]      这个时候题目有一个重要的 提示 “在一行中输出第一次出现的最长连续递增子序列”  

什么!!第一次。这可难办了 因为数数的序列其实并不是有序的 那我在排序时候可想而知 我不知道谁才是第一子序列,自然会在这里栽跟头。这里当然有两种办法,第一种建一个标记数组 map<deque<int>,int>,第二个 直接在存储上面搞。

我选择了第二个 我把 deque 定义的时候修改为 deque<pair<int,int> >[10000+10] 第一个参数是存元素的 第二个参数是存这个元素的所在组的位置。但是 这是不可取的 !! 为什么?因为题目中 1五个零就是 10W的数据量 ,双端队列数组就相当于是一个 行已知 列未知的二维数组, 这时候即便完成也一定会报 内存超限 【想想二维数组 再想想10W数据量 , 然后往sh双端里插入了pair 然后还开了 100000+10 的空间】

 

显然以上方法是不可取的 ,我们可以来欣赏一下shan上面完成的代码。 【内存超限 不可取】

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
deque<pair<int,int> > f[100000 + 10];

int cnt = 0;
int x;

bool cmp(deque<pair<int,int> >A, deque<pair<int, int> >B) {
	if (A.size() < B.size()) return false;

	else if (A.size() == B.size() && A.front().second > B.front().second) return false;
	return true;
	
}

int main() {

	scanf("%d", &x);
	int tmp;
	for (int i = 0; i < x; i++) {
		int inp;
		scanf("%d", &inp);
		if (i == 0) {
			tmp = inp;
			f[cnt].push_back({inp,cnt});
		}
		else {
			if (inp <= tmp) {
				i = inp;
				cnt++;
				f[cnt].push_back({ inp,cnt });
			}
			else {
				f[cnt].push_back({ inp,cnt });
			}
		}
		tmp = inp;
	}
	sort(f, f + cnt, cmp);
	for (int i = 0; i < f[0].size(); i++) {
		i == 0 ? printf("%d", f[0][i]) : printf(" %d", f[0][i]);
	}
	system("pause");
	return 0;
}

 

7-7 最长连续递增子序列(20 分) 普通STL解出

 



转折-- 双变量 **成功

难道 这就无解了吗 看看钟表 凌晨 2:45 分 算了 明天起来再说吧! 躺在床上睡不着,都说睡觉要在 24:00 -- 3:00 才有益。睡不着就会胡思乱想。想着想着 突然想到 不需要数组 不需要sort 只需要 两个 deque<int>的变量即可。········【睡着了】

·····早晨 8:00 :

拿出了题目想到了半夜的思路 就试了一下。

思路是这样的 :

1 . 定义两个 deque<int> 的变量 一个为答案变量 一个为临时变量A 。

2 .定义 临时变量B 存储上一次 输入的值。

2.1. 考虑到 临时变量B第一次要单独处理。

3.接着每次输入[除去第一次] 都用现输入的值和临时变量B相比较 如果比临时变量大则 更新临时变量B 同时把 输入的值放入临时变量A之中(尾插) 

3.1.如果临时变量小于等于 输入的值 那么 判断临时变量A的 size()是不是 大于(没有等于,为什么见 3.2.)答案变量的size(),如果大了就更新,接着执行 临时变量A.clear(); 再把刚刚输入的值放入临时变量接着下一次循环。如果小了就不更新,接着执行 临时变量A.clear(); 再把刚刚输入的值放入临时变量接着下一次循环。

3.2. 没有等于源于 题目中 “在一行中输出第一次出现的最长连续递增子序列” 我们知道我们是从头往后去遍历的,那么
假定我们 前面已经得到一个长度为 5 的连续序列 那一定就是最先出现的长度为5的子序列 如果后面又出现 临时bian变量的序列长度为 5 那么 它就不可能代替答案序列 成为答案。因为以己有比它优先的长度为5的序列。

 

就是这样核心思路核心的代码出来了:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

class firstq {
public:
	deque<int> f;   // 答案变量
	deque<int> ftmp;  // 临时变量A

	int cnt = 0; // 第一次更新策略
	int x;  // 数据量

	int F() {

		scanf("%d", &x);
		int tmp;  // 临时变量B

		for (int i = 0; i < x; i++) {
			int inp;
			scanf("%d", &inp);
			if (i == 0) {
				tmp = inp;
				ftmp.push_back(inp);
			}
			else {
				if (inp <= tmp) {
					if (cnt == 0) f = ftmp;  // 第一次更新策略使用地方
					else if (cnt&&f.size() < ftmp.size()) f = ftmp;
					cnt++;  // 第一次更新策略唯一修改地方
					ftmp.clear();
					ftmp.push_back(inp);
				}
				else {
					ftmp.push_back(inp);
				}
			}
			tmp = inp;
		}
		if (f.size() < ftmp.size()) f = ftmp;
		for (int i = 0; i < f.size(); i++) {
			i == 0 ? printf("%d", f[i]) : printf(" %d", f[i]);
		}
		system("pause");
		return 0;
	}
};

int main() {

	firstq A;
	A.F();
}

PS.写CLASS主要是想和其他网上程序用对数器验证。

 

                                                                                                                                         ----来自海南,在山东

                                                                                                                                                2018年8月16日