[C++知识库]练习15.输出GPLT

原题链接

解题思路：

通过遍历字符串得到所有字母的数量，进而将题目改成已知数量的字母按顺序输出

但是这个算法运行会超时，等想到改进再回来改

代码实现：

#include <stdio.h>
#include <string.h>
int main()
{
    int i,lenth,num_G=0,num_P=0,num_L=0,num_T=0;
    char ch[10001];
    gets(ch);
    lenth=strlen(ch);
    for(i=0;i<lenth;i++)
    {
        switch(ch[i])
        {
            case 'G':
            case 'g': num_G++;break;
            case 'P':
            case 'p': num_P++;break;
            case 'L':
            case 'l': num_L++;break;
            case 'T':
            case 't': num_T++;break;
            default:break;
        }
    }
    //题目变成：给定数量按顺序输出
    while(lenth)
	{
		if(num_G!=0)
		{	
            printf("G");
            num_G--;	
        }
		if(num_P!=0)
		{	
            printf("P");	
            num_P--;	
        }
		if(num_L!=0)
		{	
            printf("L");	
            num_L;	
        }
		if(num_T!=0)
		{	
            printf("T");	
            num_T--;	
        }
		if(num_G==0 && num_P==0 && num_L==0 && num_T==0)
			lenth=0;
	}
	printf("\n");
    return 0;
}

改进了一个测试点，减少了几次循环，但是还是超时

#include <stdio.h>
#include <string.h>
int min(int a,int b,int c,int d)
{
    int min_num;
    min_num=a;
    if(b<min_num)min_num=b;
    if(c<min_num)min_num=c;
    if(d<min_num)min_num=d;
    return min_num;
}
int main()
{
    int i,lenth,min_num,num_G=0,num_P=0,num_L=0,num_T=0;
    char ch[10001];
    gets(ch);
    lenth=strlen(ch);
    for(i=0;i<lenth;i++)
    {
        if(ch[i]=='G'||ch[i]=='g') num_G++;
        if(ch[i]=='P'||ch[i]=='p') num_P++;
        if(ch[i]=='L'||ch[i]=='l') num_L++;
        if(ch[i]=='T'||ch[i]=='t') num_T++;
    }
    //题目变成：给定数量按顺序输出
    min_num=min(num_G,num_P,num_L,num_T);
    for(i=0;i<min_num;i++)
        printf("GPLT");
    num_G-=min_num,num_P-=min_num,num_L-=min_num,num_T-=min_num;
    while(num_G!=0||num_P!=0||num_L!=0||num_T!=0)
    {
        if(num_G!=0)
		{
            printf("G");
            num_G--;
        }
		if(num_P!=0)
		{
            printf("P");
            num_P--;
        }
		if(num_L!=0)
		{
            printf("L");
            num_L;
        }
		if(num_T!=0)
		{
            printf("T");
            num_T--;
        }
    }
	printf("\n");
    return 0;
}