使用 C 在两个数组中查找第一个相同的大写字母

Question

我试过运行这段代码，但返回 NULL，哪一部分是错误的？正确的输出应该是“THU”，因为 'D' 是第四个大写字母。

完整代码如下：

#include <stdio.h>

char *day(char* s1, char* s2) {
    char* week[] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};
    int stop = 1;
    char ans = 0;

    while (*s1 && stop) {
        while (*s2) {
            if (*s1 == *s2 && *s1 >= 'A' && *s1 <= 'Z') {
                ans = *s1;
                stop = 0;
                break;
            }
            s2++;
        }
        s1++;
    }

    return week[ans - 'A'];
}

int main(void) {
    printf("%s\n", day("3485djDkxh4hhGE", "2984akDfkkkkggEdsb"));
    return 0;
}

Answer 1

我看到你是运行 s2 中每个字符的内循环，然后 s2 结束。之后我们必须再次将 s2 重置为开头。因此，我将它存储在 temp 中，并在你为 s1 中的每个下一个字符开始时重置为 s2。我测试了这段代码，我看到 THU 作为输出。

 char* day(char* s1, char* s2)
    {
    char* week[7] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};
    int stop = 1;
    char ans = 0;
        char* temp = s2;
    while (*s1 && stop) {
        while(*s2) {
            if (*s1 == *s2 && *s1 >= 'A' && *s1 <= 'Z') {
                ans = *s1;
                stop = 0;
                break;
            }
            s2++;
            cout << *s2 <<endl;
        }
        s1++;
        s2=temp;
    }
    return week[ans - 'A'];
    }

Answer 2

@rootkonda () 的回答解释了为什么代码不起作用。我将解决其他问题并提出替代实施方案。

根据输入，您的代码有非法（又名未定义）行为。

如果输入是"aI"和"bI"，你会做：

return week['I' - 'A]

这是

return week[8];

所以你越界访问了数组。

如果两个字符串没有共同的大写字母，也会出现类似的问题。然后你做：

return week[0 - 'A'];  // bad....

您的代码应该可以毫无问题地处理此类情况。

由于描述了任务，唯一有效的大写字母是 'A', 'B', ..., 'G'。

您当前的代码针对 s1 中的每个字母检查 s2 的内容。这导致 O(N^2) 复杂度，即当匹配的大写字母接近 s1.

末尾时，长字符串的性能不佳

下面是一个提案，首先分析s1并为大写字母生成记分牌。然后它在使用记分板时分析 s2。复杂度为 O(N)。

char *day(char* s1, char* s2) 
{
    char* week[7] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};

    int capitalLettersFound[7] = {0};  // Scoreboard for 'A' .. 'G'
    
    while (*s1) 
    {
        if (*s1 >= 'A' && *s1 <= 'G') 
        {
            // Update scoreboard
            capitalLettersFound[*s1 - 'A'] = 1;
        }
        ++s1;
    }
    
    while (*s2) 
    {
        if (*s2 >= 'A' && *s2 <= 'G' && capitalLettersFound[*s2 - 'A'] == 1) 
        {
            // Match found - return string
            return week[*s2 - 'A'];
        }
        ++s2;
    }

    // No match found
    return "No matching capital letters found";
}

使用 C 在两个数组中查找第一个相同的大写字母

Find the first same capital letter in two arrays using C

c

null

pointers