ID Codes UVA 146（求字典序比當(dāng)前字符串小的最大字符串）
來源：程序員人生 發(fā)布時(shí)間：2014-10-08 19:54:35 閱讀次數(shù)：3138次
說說：
題意其實(shí)很簡單，就是給你一個(gè)由小寫英文字母組成的字符串，然后讓你求字典序比當(dāng)前字符串小的最大的字符串。解法的話，就是從字符串的末尾開始遍歷，若得到的子串已經(jīng)是該字串所能得到的最小字典序，則繼續(xù)往前遍歷。否則，先在子串中，找到比原字串的首字符小的最大字符，將兩者交換位置。然后將除首字符以外的其他字串排列獲取最大字典序的子串即可。具體方案，看源代碼好了。
源代碼：
#include <stdio.h>
#include <string.h>
#define MAX 50+5
char ID[MAX];
int ismin(char*);//判斷當(dāng)前子串是否為最小字典序
void getans(char*);//獲取比當(dāng)前字符串小的最大字符串
int main(){
int i,len,offset,NO;
char* p;
// freopen("data","r",stdin);
while(scanf("%s",ID)){
if(ID[0]=='#')
break;
len=strlen(ID);
NO=1;
for(i=2;i<=len;i++){//從字符串末尾開始遍歷
p=&ID[len-i];
if(!ismin(p)){
getans(p);
NO=0;
break;
}
}
if(NO)
printf("No Successor
");
else
printf("%s
",ID);
}
return 0;
}
int ismin(char* p){
int i,len;
len=strlen(p);
for(i=1;i<len;i++)
if(p[i]>p[i-1])
return 0;
return 1;
}
void getans(char* p){
int i,len,pos,j;
char temp;
len=strlen(p);
for(i=1;i<len;i++)//首先得到比當(dāng)前首字符小的字符位置
if(p[i]>p[0]){
pos=i;
break;
}
for(i++;i<len;i++)
if(p[i]<p[pos]&&p[i]>p[0])//獲取比當(dāng)前首字符小的最大字符的位置
pos=i;
temp=p[0];
p[0]=p[pos];
p[pos]=temp;
p++;
len--;
for(i=1;i<len;i++)//將除首字符以外的子串排列獲得最大字典序
for(j=0;j<len-i;j++)
if(p[j]>p[j+1]){
temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
}
return ;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
