时间戳

首页 > 解决方案 > 用 C 解决这个问题时的时间限制

c - 用 C 解决这个问题时的时间限制

问题描述

上 下

比比还想挑战乔乔和莉莉。她有一个长度为 N 的字符串 S。字符串可以包含大写和小写字符。然后她会从字符串的开头开始迭代，如果第K个字符是大写字符，那么她将改变它之后的所有字符，使得大写字符变为小写字符，小写字符变为大写字符。迭代结束后，她会问 Jojo 和 Lili 是什么字符串。

格式输入

1.输入的第一行将包含一个整数T，即测试用例的数量。

2.每个测试用例将包含一个字符串S和一个整数N作为它的长度。

格式输出

对于每个测试用例，打印“Case #X:”（X 以 1 开头）。然后在同一行上，在迭代后打印字符串。

约束

1 <= T <= 10

1 <= N <= 100000

该字符串将仅由大写和小写字符组成。

这是我的解决方案。但它不断得到TLE。

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main(){
int room,len;

scanf("%d",&room);
char words[100000];

for(int i = 0; i<room; i++){
    scanf("%s %d",words,&len);
    char next[100000];
    int j = 0;

    printf("Case #%d: ",i+1);
    while(j<len){
        int k = j+1;
        if(isupper(words[j])){
            while(k<len){
                if(isupper(words[k])){
                    words[k] = tolower(words[k]);
                }else{
                    words[k] = toupper(words[k]);
                }
                k++;
            }
        }
        //printf("%c",words[j]);
        j++;
    }
    printf("%s",words);
    printf("\n");

}

return 0;
}

需要帮助以获得更好的解决方案。

我认为 TLE 来自嵌套循环，但如果没有嵌套循环，我无法弄清楚。

标签： cperformance

解决方案

在“新算法”部门 - 您已经按照说明实现了算法。但是，这意味着您要花费大量时间（我猜大部分时间）循环遍历字符串，更改字符的大小写，可能会多次。你实际上不需要这样做。保留您找到的大写字符数的计数器，最初设置为零。当你检查一个角色时，检查计数器。如果计数器是奇数（即if (counter & 1)...），则反转您当前正在查看的字符的大小写（将大写变为小写，从小写变为大写）。完成后，测试您当前正在查看的字符是否为大写（可能刚刚更改为大写）。如果是这样，增加计数器。然后继续下一个字符。

这可以在原地和单程中完成，无需任何嵌套循环。

所以你在字符串上的循环看起来像

for (i = 0, counter = 0 ; i < strlen(string) ; ++i)
  {
  if (counter & 1)                     /* if counter is odd */
    if (isupper(string[i]))            /* if character [i] is upper case */
      string[i] = tolower(string[i]);  /* convert character [i] to lower case */
    else
      string[i] = toupper(string[i]);  /* convert character [i] to upper case */

  if(isupper(string[i]))               /* if character [i] is now upper case */
    counter += 1;                      /* increment the counter */
  }

祝你好运。

推荐阅读