ARTES #023

ARTES 023

Este é o artigo 23

Pergunta sobre algoritmo de algoritmo

72. Editar distância

Dificuldade ** Difícil **

Dadas duas palavras word1 e word2, encontre o número mínimo de operações necessárias para converter word1 em word2.

Você tem as seguintes 3 operações permitidas em uma palavra:

Exemplo 1:

Exemplo 2:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Eu não resolvi totalmente essa questão sozinho. Então procurei a resposta e descobri que era necessária programação dinâmica. Eu nunca havia estudado programação dinâmica em profundidade antes. Aproveitei a oportunidade para estudá-lo cuidadosamente e descobri que a programação dinâmica não é realmente fácil de entender. Depois de lê-lo por dois dias, descobri que havia acabado de começar. Ao aprender programação dinâmica, é recomendável ler primeiro a “Ilustração do Algoritmo”. A explicação da programação dinâmica na Ilustração de Algoritmos é relativamente fácil de entender e, em seguida, pesquise informações na Internet para ajudá-lo a entender. A programação dinâmica não é algo que pode ser entendido de uma só vez. Você ainda precisa praticar mais.

Em relação a esta questão do algoritmo, esta é relativamente boa: https://blog.csdn.net/pipisorry/article/details/46383947

Além da programação dinâmica, esse problema também pode ser resolvido recursivamente.

Solução

Idioma: C

static inline int min(int a, int b)
{
    return a < b ? a : b;
}

 int minDistance(char* word1, char* word2)
{
    int i, j;
    int len1 = strlen(word1);
    int len2 = strlen(word2);
    int *table = malloc((len1 + 1) * (len2 + 1) * sizeof(int));
    int **dp = malloc((len1 + 1) * sizeof(int *));
    for (i = 0; i < len1 + 1; i++) {
        dp[i] = table + i * (len2 + 1);
    }
    
    for (i = 0; i < len2 + 1; i++) {
        dp[0][i] = i;
    }
    for (i = 0; i < len1 + 1; i++) {
        dp[i][0] = i;
    }
    
    for (i = 1; i < len1 + 1; i++) {
        for (j = 1; j < len2 + 1; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
            }
            

        }
    }
    return dp[len1][len2];
}

Revisão

Este artigo apresenta principalmente vários conhecimentos importantes de programação que os iniciantes em programação devem dominar: https://dandan2009.github.io/2019/01/25/the-main-pillars-of-learning-programming/

DICAS

Esta semana resolvemos os princípios da criptografia assimétrica, https e assinaturas iOSAPP: https://dandan2009.github.io/2019/01/24/certificate-rsa/

Compartilhar

Como desenvolvedor iOS, você ainda precisa praticar algoritmos. Além dos algoritmos, você ainda precisa atualizar os conhecimentos básicos relacionados à informática. Embora na maior parte do desenvolvimento usemos o sistema que é encapsulado diretamente e raramente encontramos situações em que escrevemos algoritmos e redes por conta própria. A razão pela qual você raramente o encontra é porque ainda está na superfície e não vai fundo o suficiente. Por exemplo, para otimizar o iOS, você precisa entender coisas relacionadas ao sistema operacional e observar alguns códigos excelentes e a implementação do código-fonte subjacente. Se você não dominar o conhecimento básico de algoritmos e computadores, descobrirá que a otimização do iOS não pode ser feita. Portanto, acho que qualquer programador deveria aprender noções básicas de informática, que são coisas dos nossos cursos universitários, como sistemas operacionais de computadores, redes de computadores, algoritmos e estruturas de dados. Não é que essas coisas sejam inúteis, mas você ainda está na superfície da programação e não se aprofundou nela.