主页 / coding / 问题 / 79322136
Accepted
Haru Hoshizora
Asked: 2025-01-02 02:36:58 +0800 CST

为什么整数即使位置不变也会有不同的值

  • 772

我试图解决一个编码问题，内容是：

编写一个替代版本，删除与字符串“.”中的任何字符匹配的squeeze(s1, s2)每个字符。s1s2

好吧，我确实对其进行了编码，并且是可用的版本。

#include <stdio.h>

char s1a[1001], s2a[1001];

void squeeze() {
    int i, j, k;
    extern char s1a[], s2a[];

    for (i = 0; s2a[i] != '\0'; i++) {
        for (k = j = 0; s1a[j] != '\0'; j++) {
            if (s1a[j] != s2a[i]) s1a[k++] = s1a[j];
        }
        s1a[k] = '\0';
    }
    printf("%d/n", k); /*k's value*/
}

int main() {
    int c, s1 = 0, i = 0, j = 0;
    extern char s1a[], s2a[];

    while ((c = getchar()) != EOF && i < 1000) {
        if (c != '\n' && s1 == 0) {
            s1a[i++] = c;
        }
        else if (c == '\n' && s1 == 0) {
            s1a[i] = '\0';
            i = 0;
            s1++;
        }
        else if (c != '\n' && s1 == 1) {
            s2a[j++] = c;
        }
        else if (c == '\n' && s1 == 1) {
            s2a[j] = '\0';
            j = 0;
            squeeze();
            printf("%s\n", s1a);
            s1a[0] = '\0';
            s2a[0] = '\0';
            s1 = 0;
        }
    }
}

我确实输入了“hello\nhell\n”。

它工作正常，但此代码中的第 13 行在打印 k（第 15 行）之前位于两个 for 循环之外，因此当时它将 k 打印为 5 而当我在现在的位置添加字符串终止符时，它将 k 打印为 1。它工作正常并打印“o”，但之前它打印的是“ooooo”。

编辑：问题出在我的理解上，因为 s1a 末尾有 5 个 o，所以在收缩后不终止时 k 是 5。

c

2 个回答

  1. 作为附加的（长）注释，您的代码具有 O(m * n) 运行时复杂度（m即第一个字符串的长度和n第二个字符串的长度）。对于长字符串，可以通过为第二个列表创建查找表来改进这一点，以使检查字符是否在第二个字符串中成为 O(1) 操作而不是 O(n)。

    #include <stdbool.h>
#include <string.h>

void squeeze(char *s1, char *s2) {
    bool table[256] = {0};

    for (char *ch = s2; *ch; ch++) {
        table[(unsigned char)*ch] = true;
    }

    size_t j = 0;
    
    for (char *ch = s1; *ch; ch++) {
        if (!table[(unsigned char)*ch]) {
            s1[j++] = *ch;
        }
    }

    s1[j] = '\0';
}

    运行时复杂度现在可以表示为 O(max(m, n))。我们可以简化它以表明运行时复杂度是线性的。这比原来的复杂度好得多。

    • 2
  2. Best Answer

    这个问题令人困惑，因为你只展示了工作代码。你似乎在问，为什么在两次循环完成后k终止字符串时给出的答案s1a与在每次外循环结束后终止字符串的正确时间不同。

    原因是内循环预计s1a在其当前大小终止。

    如果s1a是 { h，e，l，l，o，\0}，并且您删除了'h'但没有写入新的终止符，则将剩下 { e，l，l，o，o，\0}。当您写入新的终止符时，将得到 { e，l，l，o，\0，\0}。

    因此，每次扫描是否存在字母实例时，您都只扫描字符串中仍然重要的部分，并且k永远不会到达末尾被遗弃字符的索引。

    • 1

相关问题