Лимит времени при решении этой проблемы в С

Question

Верхний нижний

Биби также хочет бросить вызов Джоджо и Лили. У нее есть строка S с длиной N. Строка может содержать прописные и строчные буквы. Затем она выполнит итерацию с начала строки, если K-й символ является заглавным, то он изменит все символы после него, так что заглавные буквы станут строчными, а строчные - заглавными. После окончания итерации она спросит Джоджо и Лили, что это за строка.

Формат ввода

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 происходит от вложенных циклов, но я не могу понять это без вложенных циклов.

Answer 1

В отделе "новый алгоритм" - вы реализовали алгоритм, как указано. Тем не менее, это означает, что вы тратите много времени (большую часть времени, я полагаю), перебирая строку, изменяя регистр символов, возможно, несколько раз. Вам на самом деле не нужно делать это. Держите счетчик числа символов в верхнем регистре, которые вы нашли, изначально установлен на ноль. Когда вы изучаете персонажа, проверьте счетчик. Если счетчик нечетный (т.е. 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 */
  }

Удачи.

Answer 2

Вы можете попробовать это с помощью некоторых волшебных указателей. Кроме того, попытайтесь разделить вашу программу на функции, чтобы каждая часть вашего кода имела четкую цель. В заключение, scanf не очень хорошее решение для получения пользовательского ввода: если пользователь вводит больше символов, чем ожидалось, это может сломать вашу программу (или вашу систему, если вы используете Windows). Я только что использовал это scan_str В качестве примера.

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

/* Helper function to swap a character case */
char swap_case(char c) {
    if(isupper(c))
        return tolower(c);

    return toupper(c);
}

/* Our iteration test case */
char*test_iterate(char*str) {
    char *p, *p0;

    /* Don't swap until first upper char is found */
    int swap = 0;

    /*
     * - Initialize both pointers to beginning of string
     * - Iterate until a 0 is found (end of string)
     * - Each iteration, "advance" pointer by one
     */
    for(p0 = p = str; *p != 0; p++) {

        /* If is upper, begin to swap case */
        if(isupper(*p))
            swap = 1;

        *p = swap ? swap_case(*p) : *p;
    }

    /* Return pointer to begining of word */
    return p0;
}

/*
 * `scanf("%s", &word)` is not good if you are serious and want to avoid memory overflow
 */
char*scan_str() {
    /* Lets begin with 10 bytes allocated */
    size_t buf_size = 10;
    char c, *word = (char*) malloc(buf_size);
    int length = 0;

    /* Iterate reading characters from `stdin` until ENTER is found */
    while( (c = getc(stdin)) != '\n' && c != EOF ) {

        /* If we need more than already allocated, allocate more (10 bytes more) */
        if((length + 1) >= buf_size) {
            buf_size += 10;
            word = realloc(word, buf_size);
            if(word == NULL)
                return "Some weird error.";
        }

        /* Save read char to our word/buffer */
        word[length] = c;
        length++;
    }

    /* Add word ending character */
    word[length] = 0;

    return word;
}

int main(void) {
    int room;

    /* Two dimensional array: list of string pointers */
    char**tests;

    /*
     * Use `scanf` to read an integer
     * It's still not good enough, as you need this weird `%*c` to discard ENTER inputs
     */
    printf("Insert number of tests to do:\n");
    scanf("%d%*c", &room);

    /* Allocate memory for `tests`: array of pointers to strings */
    tests = (char**) malloc(sizeof(char*) * room);

    /* Get input from user */
    for(int i = 0; i < room; i++) {
        printf("Insert test case #%d:\n", i + 1);
        tests[i] = scan_str();
    }

    /* Print results and free each test memory */
    for(int i = 0; i < room; i++) {
        printf("Case #%d: %s\n", i + 1, test_iterate(tests[i]) );
        free(tests[i]);
    }

    /* Free `tests` array */
    free(tests);

    return 0;
}