ARTES #022

ARTS é uma atividade iniciada por 由左耳朵耗子--陈皓: Faça pelo menos uma pergunta sobre o algoritmo leetcode toda semana, leia e comente pelo menos um artigo técnico em inglês, aprenda pelo menos uma habilidade técnica e compartilhe um artigo com opiniões e pensamentos. (Ou seja, Algoritmo, Revisão, Dica e Compartilhamento são chamados de ARTS) e persistem por pelo menos um ano.

ARTES 022

Este é o artigo 22

Pergunta sobre algoritmo de algoritmo

648. Substituir palavras

Dificuldade Média

Em inglês, temos um conceito chamado root, que pode ser seguido de algumas outras palavras para formar outra palavra mais longa – vamos chamar essa palavra de successor. Por exemplo, a raiz an, seguida de other, que pode formar outra palavra another.

Agora, dado um dicionário que consiste em muitas raízes e uma frase. Você precisa substituir todos os successor da frase pelo root que a forma. Se um successor tiver muitos roots que podem formá-lo, substitua-o pela raiz com o comprimento mais curto.

Você precisa gerar a frase após a substituição.

Exemplo 1:

Nota:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Solução

Idioma: C

/**判断str1是否以str2开头
 * 如果是返回1
 * 不是返回0
 * 出错返回-1
 * */
int is_begin_with(const char * str1,char *str2){
    if(str1 == NULL || str2 == NULL)
        return -1;
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    if((len1 < len2) ||  (len1 == 0 || len2 == 0))
        return -1;
    char *p = str2;
    int i = 0;
    while(*p != '\0')
    {
        if(*p != str1[i])
            return 0;
        p++;
        i++;
    }
    return 1;
}

/*方法，调用C库函数,*/
char* join(char *s1, char *s2){
    char *result = malloc(strlen(s1)+strlen(s2)+1);//+1 for the zero-terminator
    if (result == NULL)
        return NULL;
    
    strcpy(result, s1);
    strcat(result, s2);
    
    return result;
}

char* replaceWords(char** dict, int dictSize, char* sentence) {
    int i = 0;
    //先处理dict，把dict中词根 处理为最短词根
    while (i < dictSize) {
        char* str2 = dict[i];
        if (str2 == NULL) {
            i++;
            continue;
        }
        
        int j = i+1;
        while (j < dictSize) {
            char* str1 = dict[j];
            if (str1 == NULL) {
                j++;
                continue;
            }
            
            if (strcmp(str1, str2) == 0) {
                dict[j] = NULL;
                j++;
                continue;
            }
            
            if (is_begin_with(str1,str2)==1) {
                dict[j] = NULL;
                j++;

            }
            j++;
        }
        i++;
    }
    

    //分割字符串进行替换
    char * re = "";
    char * pch = strtok(sentence, " ");
    while (pch != NULL){
        if (strlen(re) > 0){
             re = join(re," ");
        };
        
        
        int j=0;
        while (j < dictSize) {
            char* str1 = dict[j];
            if (str1 == NULL) {
                j++;
                continue;
            }

            if ((strcmp(pch, str1) != 0) && (is_begin_with(pch,str1)==1)) {
                pch = str1;
                break;
            }
            j++;
        }
        re = join(re,pch);
        pch = strtok(NULL, " ");
        
    }
    return re;
}

Revisão

https://dandan2009.github.io/2018/12/28/exposing-NSDictionary/

DICAS

Dois controles foram de código aberto esta semana: Banner de rolagem circular altamente personalizado: https://github.com/dandan2009/DDCircleScrollViewBanner Controle de janela pop-up, suporta texto, imagens, gráficos e pop-ups de visualização personalizada: https://github.com/dandan2009/DDPopUpView

Compartilhar

Hoje fiz uma pergunta a um entrevistador: Por que o AF2.x precisa de threads residentes?

Isso é o que este código faz:

+ (void)networkRequestThreadEntryPoint:(id)__unused object {
     @autoreleasepool {
          [[NSThread currentThread] setName:@"AFNetworking"];

          NSRunLoop *runLoop = [NSRunLoop currentRunLoop];
          [runLoop addPort:[NSMachPort port] forMode:NSDefaultRunLoopMode];
          [runLoop run];
     }
}

+ (NSThread *)networkRequestThread {
     static NSThread *_networkRequestThread = nil;
     static dispatch_once_t oncePredicate;
     dispatch_once(&oncePredicate, ^{
          _networkRequestThread =
          [[NSThread alloc] initWithTarget:self
               selector:@selector(networkRequestThreadEntryPoint:)
               object:nil];
          [_networkRequestThread start];
     });

     return _networkRequestThread;
}

Como resultado, vários entrevistados deram respostas incorretas e muitas respostas na Internet também estavam incorretas. Aqui está um resumo:

AF2.x usa NSURLConnection para iniciar solicitações de rede. NSURLConnection foi projetado para ser enviado de forma assíncrona. Depois de chamar o método start, NSURLConnection criará alguns novos threads e usará o CFSocket subjacente para enviar e receber solicitações. Depois que alguns eventos são enviados e recebidos, o Runloop do thread original é notificado para retornar o evento. Mas o tópico original pode ter sido lançado.

Para garantir que o thread original não seja liberado e para garantir a recepção normal do método de retorno de chamada NSURLConnectionDelegate, é necessário abrir um thread para cada solicitação e manter o thread ativo. Há muitos threads para manter ativos e a sobrecarga é muito alta. Portanto, você só precisa manter um thread fixo ativo, iniciar solicitações e receber retornos de chamada nesse thread.