刷题记录:牛客NC15128老子的全排列呢

传送门:牛客

题目描述:

老李见和尚赢了自己的酒，但是自己还舍不得，所以就耍起了赖皮，对和尚说，光武不行，
再来点文的，你给我说出来1-8的全排序，我就让你喝，这次绝不耍你，你能帮帮和尚么？

一道题面清晰的要求求全排列的题目,有dfs和stl两种方法

首先是dfs:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
int vis[100];
int a[100];
int dfs(int n) {
/*我们全排列过程中是没有重复数字的,因此我们设了一个vis数组帮助判断该数字目前有
没有加入答案中.注意这里必须填入一个答案数组中,最后一起输出,不能想当然的直接输出
因为dfs是先遍历到最后,然后回来的,所以会出现12345678,87等等类似没有前缀的问题
*/
	for(int i=1;i<=8;i++) {
		if(n!=8&&vis[i]==0) {
			a[n]=i;
			vis[i]=1;
			dfs(n+1);
			//记住要回溯
			vis[i]=0;
			a[n]=0;
		}
		//因为末尾不能有空格,所以特判末尾
		if(n==8&&vis[i]==0){
			a[n]=i;
			for(int i=1;i<=n;i++) {
				if(i==n) printf("%d\n",a[i]);
				else printf("%d ",a[i]);
			}
		}
	}
	return true;
}
int main() {
	memset(vis,0,sizeof(vis));
	dfs(1);
	return 0;
}

在懂得dfs的原理之后,c++还为我们提供了一个stl的方法,可以快速的求出全排列的方法

1. 这里用到了算法类函数next_permutation，这个函数就是让一个排列变成全排列的下一项。
2. 对应的还有pre_permutation(用来求上一个全排列)
3. 这个函数是有返回值的，如果换得了（没到倒序排列），就返回true。换不了了（已经是倒序了），就返回false。

下面是具体的代码实现

#include <iostream>
#include <algorithm>
#include  <string>
using namespace std;
int main() {
    int a[8]={1,2,3,4,5,6,7,8};
    while(next_permutation(s.begin(), s.end()) {
        for (int i = 0; i < 8; i++) {
            cout << s[i];
            if (i != 7) cout << " ";
        }
        cout << endl;
    } 
    return 0;
}