面试 打印输出全部出栈次序

缘起

据说下面是一道大厂的面试题

1
1~n 是入栈顺序, 要你输出所有可能的出栈顺序

遗憾的是——找不到oj提交此题.

分析

我们知道——一共有卡塔兰数种合法的出栈次序(【1】), 但是本面试题要求我们输出所有合法的出栈次序. 其实本题就是n个1和n个-1（1代表入栈，-1代表出栈）,只要我们确定了合法的±1序列（长2n）则直接模拟即可. 那么什么叫做合法的±1序列? 其实就是这个序列的部分和不能<0 （<0的话表示栈已经空了, 你还出栈）

显然使用回溯法（即dfs）, 每次决定长度为2n的数量的第i个位置的值. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include "stdafx.h"
#include <stdio.h>
#include <stack>
using namespace std;
#include <string.h>
#define LOCAL

int n, ans[205], num; // 最多1~100的出栈次序

void print(int i)
{
	memset(ans+i, -1, (n*2-i+1)*sizeof(int)); // 后面全是-1
	stack<int> s; // 开始模拟
	int x = 1;
	for (int i = 1; i<=2*n; i++) // 读取±1序列, 模拟整个过程
	{
		if (~ans[i]) // 入栈
		{
			printf("%d入栈.\n", x);
			s.push(x);
			x++;
		}
		else // 出栈
		{
			printf("%d出栈.\n", s.top());
			s.pop();
		}
	}
	puts("");
}

void dfs(int i, int cnt, int sum) // 决定a[i], a[i]只有1或者-1两种选择, cnt是迄今（不包括a[i], 即不包括当前步骤）为止1的个数, sum是迄今（不包括a[i], 即不包括当前步骤）为止的部分和
{
	if (cnt==n) // 得到一组解了
	{
		printf("第%d种合法次序如下:\n", ++num);
		print(i); // 打印解
		return;
	}
	if (sum) // 如果能出栈
	{
		ans[i] = -1; // 决定出栈
		dfs(i+1, cnt, sum-1);
	}
	ans[i] = 1; // 决定入栈
	dfs(i+1, cnt+1, sum+1);
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	dfs(1,0,0);
	return 0;
}

参考

【1】https://yfsyfs.github.io/2019/10/01/hdu-1023-Train-Problem-II-%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0-%E6%A0%88/