Início / coding / Perguntas / 79322136
Accepted
Haru Hoshizora
Asked: 2025-01-02 02:36:58 +0800 CST

Por que um inteiro tem valor diferente mesmo quando sua posição não é alterada

  • 772

Eu estava tentando resolver uma questão de codificação que diz:

Escreva uma versão alternativa squeeze(s1, s2)que exclua cada caractere em s1que corresponda a qualquer caractere na string s2.".

Bem, eu codifiquei e a versão funcional é.

#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;
        }
    }
}

Eu digitei "hello\nhell\n".

Funciona bem, mas a 13ª linha neste código estava fora dos dois loops for antes, onde print k (na 15ª linha) está, então ele estava imprimindo k como 5 e quando adicionei o terminador de string onde está agora, ele imprime k como 1. Ele funciona bem e imprime "o", mas antes ele estava imprimindo "ooooo".

Edição: O problema, pelo meu entendimento, era que s1a tinha 5 o's no final, então k era 5 quando não terminava depois de ser reduzido.

c

2 respostas

  1. Como um comentário (longo) adicionado, seu código tem complexidade de tempo de execução O(m * n) ( msendo o comprimento da primeira string e no comprimento da segunda). Isso pode ser melhorado para strings longas criando uma tabela de consulta para sua segunda lista para tornar a verificação se um caractere está na segunda string uma operação O(1) em vez de 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';
}

    A complexidade do tempo de execução agora pode ser expressa como O(max(m, n)). Poderíamos simplificar isso para afirmar que a complexidade do tempo de execução é linear. Isso é muito melhor do que a complexidade original.

    • 2
  2. Best Answer

    A questão é confusa porque você está mostrando apenas o código funcional. Você parece estar perguntando por que kdeu uma resposta diferente quando encerrou a s1astring após ambos os loops serem concluídos em comparação ao tempo correto em que você a encerrou após cada passagem do loop externo.

    O motivo é porque o loop interno espera s1aser encerrado em seu tamanho atual.

    Se s1afosse { h, e, l, l, o, \0}, e você removesse o 'h'mas não escrevesse um novo terminador, você ficaria com { e, l, l, o, o, \0}. Quando você escreve um novo terminador, obtenha { e, l, l, o, \0, \0}.

    Então, cada vez que você verifica se há instâncias de uma letra, você verifica apenas a parte da string que ainda importa e knunca alcança os índices dos caracteres abandonados no final.

    • 1

relate perguntas