ARTES #019

ARTS22 de dezembro de 2018 às 04:523 min read

ARTES #019

简体中文 العربية English Español Bahasa Indonesia Português

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 019

Este é o artigo 19

Pergunta sobre algoritmo de algoritmo

804. Palavras exclusivas em código Morse

Dificuldade Fácil

O Código Morse Internacional define uma codificação padrão onde cada letra é mapeada para uma série de pontos e traços, como segue: "a" mapeia para ".-", "b" mapeia para "-...", "c" mapeia para "-.-." e assim por diante.

Por conveniência, a tabela completa das 26 letras do alfabeto inglês é fornecida abaixo:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

Agora, dada uma lista de palavras, cada palavra pode ser escrita como uma concatenação do código Morse de cada letra. Por exemplo, “cba” pode ser escrito como “-.-…–…”, (que é a concatenação “-.-.” + “-…” + “.-”). Chamaremos essa concatenação de transformação de uma palavra.

Retorne o número de transformações diferentes entre todas as palavras que temos.



Example:
Input: words = ["gin", "zen", "gig", "msg"]
Output: 2
Explanation: 
The transformation of each word is:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."

There are 2 different transformations, "--...-." and "--...--.".

Nota:

O comprimento das palavras será no máximo 100.
Cada palavra[i] terá comprimento no intervalo [1, 12].
palavras[i] consistirão apenas em letras minúsculas.

Solução

Idioma: C

Método 1: Este é o método mais fácil de pensar, converta diretamente as palavras em Morma, compare e remova duplicações

int uniqueMorseRepresentations(char** words, int wordsSize) {
    char *morse[26] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
    
    
    //convert words to morse
    char **chatToMorse = (char **)malloc(sizeof(char*) * wordsSize);
    int index = 0;
    while (index < wordsSize) {
        char *word = words[index];
        char *charMorse = NULL;
        for (int j = 0; j <  strlen(word); j++) {
            char charter = word[j];
            char *newmorse = morse[charter - 'a'];
            
            if (charMorse == NULL) {
                char *result = malloc(strlen(newmorse)+1);
                memset(result, '\0', strlen(newmorse)+1);
                strcpy(result, newmorse);
                charMorse = result;
            }
            else{
                char *result = malloc(strlen(charMorse)+strlen(newmorse)+1);//+1 for the zero-terminator
                memset(result, '\0', strlen(charMorse)+strlen(newmorse)+1);
                strcpy(result, charMorse);
                strcat(result, newmorse);
                free(charMorse);
                charMorse = result;
            }
        }
        chatToMorse[index] = charMorse;
        ++index;
    }
    
    int falg = 0;
    for (int m =0; m < wordsSize; m++) {
        char *  ms = chatToMorse[m];
        if(ms == NULL){
            continue;
        }
        for(int n = m+1; n <wordsSize;n++ ){
            char *  ns = chatToMorse[n];
            if (ns != NULL)  {
                int res = strcmp(ms,ns);
                if (res ==0) {
                    chatToMorse[n] = NULL;
                    falg++;
                }
            }
        }
    }
    return wordsSize -falg;
}

Método 2: A ideia deste método é igual à minha, mas mais rápida que a minha. Deveria ser porque não aloca memória dinamicamente. Outra coisa é que o cálculo final da desduplicação é diferente do meu. Mas esse código é melhor que o meu porque encapsula diferentes funções no código e tem pensamento orientado a objetos.


char *transMorse(const char alphabet){
    char *morseCode[] = { ".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.." };
    return morseCode[alphabet-'a'];
}

void transMorseString(char *word, char *morseString){
    char *morseTempt;
    while(*word){
        morseTempt = transMorse(*word);
        word++;
        while(*morseTempt){
            *morseString = *morseTempt;
            morseString++;
            morseTempt++;
        }
    }
    return;
}

int uniqueMorseRepresentations(char** words, int wordsSize) {
    char morseString[100][50] = {""};
    
    for(int i = 0 ; i<wordsSize ; ++i){
        transMorseString(words[i], morseString[i]);
    }
    
    //上面的方法h都好理解，就是把字符串转为Morse码
    //下面的这个去重计算 感觉不好理解
    for(int i = 0 ; i<wordsSize ; ++i){
        for(int j = i+1 ; j<wordsSize ; ++j){
            while(wordsSize>1 && j<wordsSize && !strcmp(morseString[i], morseString[j])){
                strcpy(morseString[j], morseString[wordsSize-1]);
                --wordsSize;
            }
        }
    }
    return wordsSize;
}

Método 3: Vantagens deste método:

É mais conveniente usar o método bidimensional ao converter uma string em código de moral.
O conceito de conjunto é usado ao remover duplicatas

Especialmente o ponto 2, a ideia de reunião, não é esta situação em que a reunião é útil, mas eu não esperava por isso.


int addToSet(char** set, int setCount, char* buf);

int uniqueMorseRepresentations(char** words, int wordsSize) {
    char* morse[26] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
    char* set[100];
    int setCount = 0;
    //1. 字符串转摩尔码的时候用了二维方法的时候 比较方便
    //2. 去重的时候用到了集合(set)的概念
    int i = 0;
    for(i = 0; i < wordsSize; i++) {
        char* buf = malloc(sizeof(char) * 60);
        buf[0] = '\0';
        int j = 0;
        for(j = 0; j < strlen(words[i]); j++) {
            char* cat = strcat(buf, morse[words[i][j] - 97]);
            
            printf("add: %c %s, all is: %s", words[i][j], morse[words[i][j] - 97], cat);
        }
        setCount = addToSet(set, setCount, buf);
        printf("\n");
    }
    
    for(i = 0; i < setCount; i++) {
        free(set[i]);
    }
    
    return setCount;
}

int addToSet(char** set, int setCount, char* buf) {
    int i = 0;
    for(i = 0; i < setCount; i++) {
        printf("compare: %s %s", set[i], buf);
        if(strcmp(set[i], buf) == 0) {
            return setCount;
        }
    }
    
    set[i] = buf;
    return ++i;
}

Método 4: A ideia desse método também é muito boa. Pense em Morma como binário 0 e 1,. representa 0 e 1 representa -. Veja os comentários do código para obter detalhes


typedef struct {
    char len;
    char val;
} morseCode;

morseCode codeTable[] = {
    {2, 2}, /* a .-   10*/
    {4, 7}, /* b -... 0111*/
    {4, 5}, /* c -.-. 0101 */
    {3, 3},
    {1, 1},
    {4,13},
    {3, 1},
    {4,15},
    {2, 3},
    {4, 8},
    {3, 2},
    {4,11},
    {2, 0},
    {2, 1},
    {3, 0},
    {4, 9},
    {4, 2},
    {3, 5},
    {3, 7},
    {1, 0},
    {3, 6},
    {4,14},
    {3, 4},
    {4, 6},
    {4, 4},
    {4, 3}
};

typedef struct{
    int len;
    int val;
}morseString;

morseString getmorseString(char* s) {
    morseString str;
    str.len = 0;
    str.val = 0;

    char *p = s;
    while(*p != '\0')
    {
        char c = *p;
        if (c < 'a' || c > 'z'){
            printf("Invalid input *p = %c\n", c);
            p++;
            continue;
        }

        morseCode code = codeTable[c - 'a'];
        str.len += code.len;//记录单词转为摩尔码，也就是二进制之后的位数，当数据很长时有用，如果数据较短，比如没有超过64位或32位。但是超过之后这个就有用了
        str.val = (str.val << (code.len)) + code.val;//把str.val看成二进制数据 就容易理解了
        p++;
    }

    return str;
}

int uniqueMorseRepresentations(char** words, int wordsSize) {
    int result = -1;
    morseString stack[100];

    for(int i = 0; i < wordsSize; i++)
    {
        morseString str = getmorseString(words[i]);
        bool foundone = false;
        for (int j = 0; j <= result; j++)
        {
            // check one by one if str in stack
            // zstack[j].len == str.len 这个判断当摩尔码的二进制长度超过机器的最大字长时才有用。
            // 如果没有超过最大字长，二进制表示相等（stack[j].val == str.val），二进制的长度必然相等
            if (stack[j].len == str.len && stack[j].val == str.val) {
                foundone = true;
                break;
            }
        }

        if (!foundone)
        {
            stack[++result] = str;
        }
    }

    return result + 1;
}

Método 5: Um método mais satisfatório, usando um array bidimensional, que é mais simples que meu método de escrita.


int uniqueMorseRepresentations(char** words, int wordsSize) {
    char transBuffer[50] = {0};
    char transCode[100][50] = {0}; //Store the translation code
    char* morseCode[] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."}; // 'a' ~ 'z' Morse Code Table
    
    int j, k;
    int existFlag = 0;
    int transCodeNum = 0;               //Different translation code numbers
    for(int i=0; i < wordsSize; i++)
    {
        j = 0;
        k = 0;
        existFlag = 0;                                      //Reset the flag
        memset(transBuffer, 0, sizeof(transBuffer));        //Reset the buffer
        while(words[i][j] != '\0')
        {
            k = words[i][j] - 'a';                          //get the number of letters
            strncat(transBuffer, morseCode[k], sizeof(morseCode[k]));   //translate the letter by morseCode
            j++;
        }
        
        
        for(int z = 0; z < transCodeNum && !existFlag; z++)     //Confirm transCode has already store same code
            if(strncmp(transCode[z], transBuffer, sizeof(transBuffer)) == 0)
                existFlag = 1;
        
        if(!existFlag)                                          //if the code isn't exist, store it
            strncpy(transCode[transCodeNum++], transBuffer, sizeof(transBuffer));
        
    }
    
    return transCodeNum;
}

Revisão

Este artigo é sobre: Como se tornar um desenvolvedor de software melhor Falando sobre outras coisas além de habilidades de desenvolvimento: 1 Compreenda todo o processo de desenvolvimento. Recomenda-se que os desenvolvedores não se concentrem apenas na codificação, mas também estejam familiarizados com todo o processo de desenvolvimento, o processo de conversão de ideias vagas em soluções cuidadosamente projetadas e os testes, implantação, monitoramento, análise e melhoria após a conclusão do desenvolvimento do software. Isto permite que todos se entendam e reduzam as barreiras de comunicação causadas pela compreensão mútua do trabalho de outras pessoas. 2 Compreenda as necessidades dos clientes, comunique-se com os clientes, obtenha confiança mútua e forneça feedback oportuno sobre o progresso e os resultados aos clientes. 3 Escolha soluções ou ferramentas diferentes para trabalhos diferentes e não possa usar as competências e a experiência existentes para tudo. 4. Apoie-se nos ombros de gigantes e seja bom no uso de ferramentas de terceiros, em vez de desenvolvê-las do zero sempre. 5. Para aprender os princípios básicos do conhecimento, você não pode buscar cegamente novos conhecimentos. Você deve compreender os princípios por trás do conhecimento.

Para tradução veja: https://dandan2009.github.io/2018/12/18/how-to-become-a-better-software-developer/ Veja o texto original: https://medium.com/devtrailsio/how-to-become-a-better-software-developer-dd16072c974e

Dicas

Anteriormente, o Instruments era usado para testar o tempo de inicialização do APP. Só poderia registrar os eventos de execução de um determinado método. Agora você pode usar Signposts para registrar o tempo de execução de cada linha do código APP: Veja WWDC2018 Medindo o desempenho usando log: https://developer.apple.com/videos/play/wwdc2018/405/

Aqui está uma tradução que você pode ler: https://blog.csdn.net/tugele/article/details/81252603

O exemplo dado acima é baseado em Swift, e a versão em linguagem C pode ser usada em Objective-C:

  os_log_t log = os_log_create("com.example.your-app",  "RefreshOperations");
  os_signpost_id_t log_t = os_signpost_id_generate(log);
  
   os_signpost_interval_begin(log, log_t, "Fetch Asset");
   你的代码
   os_signpost_interval_end(log, log_t, "Fetch Asset");
   
   os_signpost_interval_begin(log, log_t, "Fetch Asset1");
   你的代码
   os_signpost_interval_end(log, log_t, "Fetch Asset1");

Cotação de recrutamento: https://readhub.cn/jobs

Google Acadêmico, Wikipedia, Google Tradutor, Gmail Web, Google Fotos, Google Docs, Google Keep, Google Earth, Google Livros, Chrome Sync, Pixiv, Comunidade Steam, lançamentos do GitHub, Pinterest, Vimeo, Yandex, Tumbl YouTube, Twitter, Facebook, Google+, Google Play, Google Drive, Blogger, alguns sites de notícias, Instagram

Aprendizagem de inglês: https://learnamericanenglishonline.com/Red Level/R1 Do.html

Descriptografar Runloop: http://mrpeak.cn/blog/ios-runloop/

reprodutor de código aberto mac: 15.000 estrelas, IINA é o reprodutor de vídeo moderno para macOS. https://github.com/lhc70000/iina

Exemplo de como ganhar dinheiro através de pequenos programas desenvolvidos: https://www.v2ex.com/t/515777

Pode acessar o Google: https://sss.cnsdhh.com/

Site para busca de cores: https://picular.co/，搜索出来的颜色是一个色系的，不是单一的一种颜色

FAQ