題目大意：給出一個字符串，輸出字符串中的字符的全排列，要求按照字典序升序輸出，不允許重復。
此題我認為沒有什么意義，因為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 閱讀(699)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索