c - 评分网站一直说我的代码超出了时间限制

Question

好吧，我尝试解决问题“Find the Cow”! [布莱恩·迪恩，2012]我发现它在“Visual Studio”和其他 IDE 中运行良好。但是在“code up”中对我的代码进行评分的网站...它一直说我的代码超出了时间限制...我的代码有问题吗？

问题是问题名称:cowfind

输入格式:

• 第 1 行:长度为 N 的括号字符串 (1 <= N <= 50,000)。

示例输入(文件cowfind.in):

)((()())())

输出格式:

• 第 1 行:Bessie 可能处于的位置数 站立——即不同索引对的数量 x < y 处存在模式 (( 在索引 x 处且 模式 )) 在索引 y 处。

示例输出(文件cowfind.out):

4

输出详细信息:

Bessie 有 4 个可能的位置，如下所示:

1.

)((()())())
 ^^   ^^

2.

)((()())())
  ^^  ^^

3.

)((()())())
  ^^     ^^

4.

)((()())())
 ^^      ^^

代码:

    #include <stdio.h>
    #pragma warning(disable:4996)
    int main() {
        char c[50000];
        int i = 0;
        int j;
        int num = 0;
        while (scanf("%c", &c[i]) == 1)i++;
        c[i] = '\0';
        i = 0;


        while (c[i + 1] != '\0') {
                if ( (c[i] == c[i + 1]) && c[i] == '(') {
                j = i + 2;
                while (c[j + 1] != '\0') {
                    if ((c[j] == c[j + 1]) && c[j] == ')') {
                        num++;
                    }
                    j++;
                }
            }
            i++;
        }

        printf("%d", num);

    }

Answer 1

对于许多这样的在线判断问题，关键是想出更好的方法来计算结果。他们不只是挑战你编写代码，而是思考如何设计更好的算法。

#include <stdio.h>


int main(void)
{
    long positions = 0; //  Count positions where Bessie may be standing.
    long opens = 0;     //  Count number of times "((" has been seen.
    char previous = 0;  //  Remember previous character.

    //  Loop reading characters.
    while (1)
    {
        //  Get next character.
        int next = getchar();

        //  If there was no next character or the line ended, we are done.
        if (next == EOF || next == '\n') break;

        //  Count the number of times "((" has been seen.
        if (next == '(' && previous == '(')
            ++opens;

        //  When we see "))", add one position for each "((" that precedes it.
        if (next == ')' && previous == ')')
            positions += opens;

        //  Remember the character for the next iteration.
        previous = next;
    }

    //  Show the result.
    printf("%ld\n", positions);
}