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

Pop Sequence

程序员文章站 2022-07-01 11:24:40
...

Pop Sequence

题目

Pop Sequence
题目地址:地址

思路

例如题目例子中可能的序列:3 2 1 7 5 6 4
可以用一种反证法,假设这个序列是存在的,我们现在模拟这个序列生成的过程,如果生成的过程与题目条件一致,则序列存在,否则,则不存在;
首先我想要3!一看堆栈里面啥都没有,只能往里面放,第一次只能放1,发现1不等于3,那就再往里面放2,还不等于,那就放3,哎,等于啦!把3拿出来,再看我们假设成立的序列,该2了,我们以看栈顶是2,是2,把2拿出来,同理,把1拿出来,这时候我们需要7了,站里面没东西了,继续往里面加,加4,不行,加5,不行,加6,不行,加7,哎可以啦,把7拿出来,然后下一个需要的是6,发现栈顶是7,不一样,继续往栈里面放,发现没东西放了,而我们现在只能拿7,达不到我们假设序列的要求,所以我们假设的序列是失败的!

综上分析:我们相当于是对假设序列的每个元素逐一分析,同时模拟入栈过程,判断每个元素是否能被堆栈返回有一个不能返回,则失败。

代码

#include"stdio.h"
#include"malloc.h"
struct Stack {
	int Data[1000];
	int Max, Now;
};
int main() {
	Stack s;
	int p_num, c_num, i, j;

	scanf("%d %d %d", &s.Max, &p_num, &c_num);/*对应M,N,K*/
	int* t;
	
	t = (int*)malloc(c_num * sizeof(int));
    /*对K遍历*/
	for (i = 0; i < c_num; i++) {
		int k = 0;
		s.Now = -1;
		int* List2;/*7,6,5,4,3,2,1*/
		int* List1;/*1,2,3,4,5,6,7*/
		List2 = (int*)malloc(p_num * sizeof(int));
		List1 = (int*)malloc(p_num * sizeof(int));
		int h;
        /*给list1和list2赋值*/
		for (h = 0; h < p_num; h++) {
			List1[h] = h + 1;
			scanf("%d", &List2[h]);
		}
        /*对每个k的每个元素遍历验证*/
		for (j = 0; j < p_num; j++) {
			
			if (s.Now == -1) {
				s.Now++;
				s.Data[s.Now] = List1[k];
				k++;
			}
			while (s.Data[s.Now] != List2[j] && s.Now < s.Max - 1) {
				if (k < p_num)
				{

					s.Now++;
					s.Data[s.Now] = List1[k];
					k++;
				}
				else
				{
					break;
				}
			}
			if (s.Data[s.Now] == List2[j]) {
				s.Now--;
			}
			else
			{
				break;
			}
		}
		/*将每个k的答案存在t中*/
		if (j == p_num) {
			t[i] = 1;
		}
		else
		{
			t[i] = 0;
		}
	}
	int f;
    /*打印答案*/
	for (f = 0; f < c_num; f++) {
		if (t[f] == 1) {
			printf("YES\n");
		}
		else
		{
			printf("NO\n");
		}
	}
	return 0;
}
相关标签: 数据结构