题目大意：给出一个字符串，输出字符串中的字符的全排列，要求按照字典序升序输出，不允许重复。
此题我认为没有什么意义，因为C++的<algorithm>中有next_permutation()函数，直接可以通过不断地求“下一个排列”得出结果，而且是可以判断重复的！但是高中信息学竞赛不允许用<algorithm>！如果不用这个函数真的好麻烦！我想到的是qsort+dfs+判重，还需要那么大的空间消耗来保存已出解！
以下是我的代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
char s[11],*s_end;
long n;
scanf("%ld",&n);
while (n--)
{
scanf("%s",s);
s_end=s+strlen(s);
sort(s,s_end);
do
printf ("%s\n", s);
while(next_permutation(s,s_end));
printf("\n");
}
}
补充：今天下午体育课的时候，突然想到一种不需要C++标准库中的函数，也不需要判重的方法，同样十分方便实现，而且复杂度很低。因为字符串一开始是已经排好序的，因此如果出现了重复，那么：要么当前生成的串与上一次生成的串字典序相同，要么比上次生成的串字典序小。因此，只要设置一个last字符串和now字符串，分别表示上次生成的串和当前正在生成的串，问题就解决了。
以下是我的代码（没有提交，有兴趣可以直接拿去尝试）：
#include<stdio.h>
#include<string.h>
const long maxlen=18;
long n,slen;
char s[maxlen],now[maxlen],last[maxlen];
bool used[maxlen];
void swap(char &a,char &b)
{
char t=a;a=b;b=t;
}
void Qsort(char *a,long begin,long end)
{
long i=begin,j=end;
char mid=a[(begin+end)/2];
do{
while(a[i]<mid) i++;
while(a[j]>mid) j--;
if(i<=j)
{
swap(a[i],a[j]);
i++;j--;
}
}while(i<=j);
if(i<end) Qsort(a,i,end);
if(j>begin) Qsort(a,begin,j);
}
void dfs(long dep)
{
if(dep>=slen)
{
if(strcmp(now,last)>0)
{
printf("%s\n",now);
strcpy(last,now);
}
return;
}
for(long i=0;i<slen;i++)
if(!used[i])
{
used[i]=true;
now[dep]=s[i];
dfs(dep+1);
used[i]=false;
}
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
scanf("%ld",&n);
for(long k=1;k<=n;k++)
{
memset(s,0,sizeof(s));
memset(now,0,sizeof(now));
memset(last,0,sizeof(last));
memset(used,0,sizeof(used));
// Clear
scanf("%s",s);
// Read In
slen=strlen(s);
Qsort(s,0,slen-1);
// Qsort
dfs(0);printf("\n");
// Dfs
}
return 0;
}
posted on 2010-01-08 13:35
lee1r 阅读(673)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：搜索