ARTES #015

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 015

Este é o artigo 15

Pergunta sobre algoritmo de algoritmo

As questões de algoritmo que fizemos esta semana foram travessia de pré-ordem, travessia de ordem e travessia de pós-ordem de uma árvore binária. Cada tipo de travessia é implementado de forma recursiva e iterativa, respectivamente. As implementações recursivas das três travessias são basicamente as mesmas, mas as implementações iterativas das três travessias são diferentes. Entre eles, a implementação iterativa da travessia pós-ordem é a mais difícil.

A diferença entre recursão e iteração: Recursão: A técnica de programação na qual um programa chama a si mesmo é chamada de recursão Iteração: Use o valor original da variável para calcular um novo valor da variável. Iteração significa que A continua chamando B.

Exemplos de histórias de filmes: Iteração - “No Limite do Amanhã” Recursão - “Início”

参见：
https://blog.csdn.net/laoyang360/article/details/7855860
Google：递归 迭代
斐波那契数列为:0,1,1,2,3,5...
//迭代实现斐波那契数列  
long fab_iteration(int index)  
{  
    if(index == 1 || index == 2)  
    {  
        return 1;  
    }  
    else  
    {  
        long f1 = 1L;  
        long f2 = 1L;  
        long f3 = 0;  
        for(int i = 0; i < index-2; i++)  
        {     
            f3 = f1 + f2; //利用变量的原值推算出变量的一个新值  
            f1 = f2;  
            f2 = f3;  
        }  
         return f3;  
    }  
}  
  
//递归实现斐波那契数列  
 long fab_recursion(int index)  
 {      
    if(index == 1 || index == 2)  
    {  
        return 1;  
    }  
    else  
    {  
        return fab_recursion(index-1)+fab_recursion(index-2);    //递归求值  
    }  
} 

Travessia de pré-ordem: nó raiz —> subárvore esquerda —> subárvore direita Travessia em ordem: subárvore esquerda —> nó raiz —> subárvore direita Travessia pós-ordem: subárvore esquerda —> subárvore direita —> nó raiz

94. Traversal de ordem de árvore binária

Dificuldade: Média

Dada uma árvore binária, retorne o percurso inorder dos valores de seus nós.

Exemplo:

**Input:** [1,null,2,3]
   1
    \
     2
    /
   3

**Output:** [1,3,2]```

**Acompanhamento:** A solução recursiva é trivial. Você poderia fazer isso iterativamente?



#### Solução

Idioma: **C**

```c
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
 

// solução recursiva implementação recursiva

int* inorderTraversal(struct TreeNode* root, int* returnSize) {

    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    
    //左子树
    int returnSizeLeft = 0;
    int *left = NULL;
    if(root->left != NULL){
        left= inorderTraversal(root->left, &returnSizeLeft);
    }
    
    //根结点
    
    //右子树
    int returnSizeRight = 0;
    int *right = NULL;
    if(root->right!= NULL){
        right = inorderTraversal(root->right, &returnSizeRight);
    }
    
    *returnSize = returnSizeLeft + returnSizeRight + 1;
    int* traversalResult=(int*)malloc((*returnSize)*sizeof(int));
    
    int index = 0;
    for (int i =0; i<returnSizeLeft; i++) {
        traversalResult[index++] = left[i];
    }
    free(left);
    
    traversalResult[index++] = root->val;
    
    for (int i =0; i<returnSizeRight; i++) {
        traversalResult[index++] = right[i];
    }
    free(right);

    return traversalResult;
}

// solução iterativa implementação iterativa

//迭代算法 iteratively
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
   struct TreeNode** traversalResult=(struct TreeNode**)malloc(1000*sizeof(struct TreeNode*));
   if (root == NULL) {
       *returnSize = 0;
       return NULL;
   }
   int *result=(int*)malloc(1000*sizeof(int));
   *returnSize = 0;
   
   int index = 0;
   struct TreeNode* p = root;
   
   while (p != NULL || index>0) {
       printf("%d",index);
       while (p != NULL) {
               traversalResult[index++] = p;
               p = p->left;
       }
       if (index >= 1) {
           p = traversalResult[--index];
           result[(*returnSize )++] = p->val;
           p = p->right;
       }
   }
   return result;
}

144. Travessia de pré-encomenda de árvore binária

Dificuldade: Média

Dada uma árvore binária, retorne o percurso preorder dos valores de seus nós.

Exemplo:

**Input:** `[1,null,2,3]`
   1
    \
     2
    /
   3

**Output:** `[1,2,3]`

Acompanhamento: A solução recursiva é trivial. Você poderia fazer isso iterativamente?

Solução

Idioma: C

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    
}

//iteratively solution 迭代解决
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    
        if (!root) {
        *returnSize = 0;
        return NULL;
    }
    
    int * result = (int *)malloc(sizeof(int) * (1000));
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * (1000));
   
    struct TreeNode* p=root;
    *returnSize = 0;
    int stackIndex = 0;
   
    while (p || stackIndex > 1) {
    
        result[(*returnSize)++] = p->val;
        
        if (p->right) {
            stack[stackIndex++]=p->right;
        }
        
        p = p->left;
        
        if (stackIndex > 0&&!p) {
             p = stack[--stackIndex];
        }
    }
    
    
    return result;
}

//recursive solution 递归解决
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    if (!root) {
        * returnSize = 0;
        return NULL;
    }
    
    //左节点
    int leftSize =  0;
    int *left = NULL;
    if(root->left){
       left =  preorderTraversal(root->left, &leftSize);
    }
    
    //右节点
    int rightSize =  0;
    int *right = NULL;
    if(root->right){
       right =  preorderTraversal(root->right, &rightSize);
    }
    
    *returnSize = leftSize + rightSize + 1;
    int * result = (int *)malloc(sizeof(int) * (*returnSize));
    
    
    int index = 0;
    
    //根节点
    result[index++] = root->val;
    
    //左节点
    for (int i =0; i<leftSize; i++) {
        result[index++] = left[i];
    }
    free(left);
    
    //右节点
    for (int i =0; i<rightSize; i++) {
        result[index++] = right[i];
    }
    free(right);
    
    return result;
}

145. Traversal de pós-ordem de árvore binária

Dificuldade: Difícil

Dada uma árvore binária, retorne a travessia postorder dos valores de seus nós.

Exemplo:

**Input:** `[1,null,2,3]`
   1
    \
     2
    /
   3

**Output:** `[3,2,1]`

Acompanhamento: A solução recursiva é trivial. Você poderia fazer isso iterativamente?

Solução

Idioma: C

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    
}

////迭代实现 iteratively solution
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    int *result = (int *)malloc(sizeof(int) * 1000);
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 1000);
    
    * returnSize  = 0;
    int stackIndex = 0;
    int *flag = (int *)malloc(sizeof(int) * 1000);//用来标记是否是第二次访问这个节点
    
    struct TreeNode* p = root;

    while (p || stackIndex > 1) {
        if (p) {
            int dex = stackIndex++;
            stack[dex] = p;
            flag[dex] = 1;
            
        }
        
        if (p->right) {
            int dex = stackIndex++;
            stack[dex] = p->right;
            flag[dex] = 0;
        }
        
        p = p->left;
        if (!p && stackIndex > 0) {
            int loop =1;
            while (loop && stackIndex>0) {
                int index = --stackIndex;
                p = stack[index];
                if (flag[index] == 1) {
                    result[(*returnSize)++] = p->val;
                    loop = 1;
                }
                else{
                    loop =0;
                }
            }
            if (stackIndex==0) {
                return result ;
            }
        }
    }
    return result;
}

//递归实现 Recursive solution
int* postorderTraversal_1(struct TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    
    int *left = NULL;
    int leftSize = 0;
    if (root->left) {
        left = postorderTraversal(root->left, &leftSize);
    }
    
    int *right = NULL;
    int rightSize = 0;
    if (root->right) {
        right = postorderTraversal(root->right, &rightSize);
    }
    
    *returnSize = leftSize + rightSize  + 1;
    int *result =  (int *)malloc(sizeof(int) * (*returnSize));
    int index = 0;
   
    for (int i = 0; i < leftSize; i++) {
        result[index++] = left[i];
    }
    
    for (int i = 0; i < rightSize; i++) {
        result[index++] = right[i];
    }
    
    result[index] = root->val;
    
    free(left);
    free(right);
    
    
    return result;
}

Revisão

Revisão apenas como um artigo: https://dandan2009.github.io/2018/11/17/accelerating-your-coding-skills/

DICAS

Esta semana, vamos resolver os conceitos relacionados às árvores binárias.

Alguns conceitos relacionados de árvores binárias:

Uma árvore binária é uma estrutura de árvore em que cada nó possui no máximo duas ramificações (ou seja, não existem nós com grau de ramificação maior que 2). Normalmente os ramos são chamados de “subárvore esquerda” ou “subárvore direita”. Os ramos de uma árvore binária têm ordem esquerda e direita e não podem ser invertidos à vontade. O i-ésimo nível da árvore binária tem no máximo 2 ^ i-1 nós

diferente das árvores comuns O número de nós de uma árvore comum é pelo menos 1, enquanto o número de nós de uma árvore binária pode ser 0; Não há limite para o grau máximo de ramificação de um nó de árvore normal, enquanto o grau máximo de ramificação de um nó de árvore binária é 2; Os nós de uma árvore comum não têm ordem esquerda ou direita, enquanto os nós de uma árvore binária têm ordem esquerda ou direita.

Árvores binárias são geralmente usadas como estruturas de dados. Um uso típico é definir uma função de rotulagem para os nós e associar alguns valores a cada nó. A árvore binária marcada desta forma pode implementar árvore de pesquisa binária e heap binário e ser usada para pesquisa e classificação eficientes.

Árvores binárias não são um caso especial de árvores Embora existam muitas semelhanças entre os conceitos de árvores e árvores binárias, são duas estruturas de dados diferentes. Porque pela definição: Uma árvore binária não é uma árvore com apenas duas subárvores nem uma árvore com no máximo duas subárvores. A principal diferença entre uma árvore e uma árvore binária é que a subárvore de um nó em uma árvore binária deve distinguir entre a subárvore esquerda e a subárvore direita. Mesmo que o nó tenha apenas uma subárvore, deve ser claramente indicado se a subárvore é a subárvore esquerda ou a subárvore direita. Quanto a uma árvore, não importa quantas subárvores ela tenha, o status de cada subárvore é o mesmo, ao contrário de uma árvore binária onde esquerda e direita são diferenciadas.

Uma árvore binária é uma árvore ordenada especial: cada nó tem no máximo duas ramificações (nós filhos), e as ramificações têm ordem esquerda e direita e não podem ser revertidas. Duas árvores binárias especiais: Árvore Binária Completa: Exceto a última camada, se todas as outras camadas estiverem cheias e a última camada estiver cheia ou faltando vários nós consecutivos à direita (observe que está à direita, não à esquerda). Árvore Binária Completa: Cada nível é completo (exceto o último nível, onde o último nível se refere ao nó folha).

Árvores binárias podem ser armazenadas usando arrays ou listas vinculadas. Se a árvore binária estiver cheia, ela poderá ser organizada de forma compacta, sem desperdiçar espaço. Se o índice de um nó for i, (assumindo que o índice do nó raiz é 0), então o índice do seu nó filho esquerdo será 2i+1, e o índice do seu nó filho direito será 2i+2; e seu nó pai (se houver) terá o índice $\frac{i-1}{2}$. Essa abordagem é mais propícia ao armazenamento compacto e melhor localização de acesso, especialmente na passagem de pré-encomenda. No entanto, requer espaço de armazenamento contínuo, portanto, muito espaço será desperdiçado ao armazenar uma árvore geral composta por n nós com altura h. Na pior das hipóteses, se cada nó de uma árvore binária com profundidade h tiver apenas um filho certo, a estrutura de armazenamento precisará ocupar 2 ^ h - 1 espaço. Na verdade, existem h nós, o que desperdiça muito espaço e é uma grande deficiência da estrutura de armazenamento sequencial.

Uma árvore binária completa armazenada em um array

Primeira travessia em profundidade Em prioridade de profundidade, queremos acessar o nó mais distante do nó raiz. Diferente da busca em profundidade do grafo, não há necessidade de lembrar cada nó visitado, pois não haverá ciclos na árvore. A travessia Pré-encomenda, Em ordem e Pós-encomenda são casos especiais de travessia Em profundidade. Consulte pesquisa em profundidade.

Travessia em largura Ao contrário da travessia em profundidade, a travessia em largura visita primeiro os nós mais próximos do nó raiz. Consulte pesquisa em largura. A travessia em largura de uma árvore binária também é chamada de travessia nível por nível. O algoritmo é implementado com a ajuda de filas.

Árvore binária Definição: A árvore binária t é um conjunto de elementos finitos (pode ser vazio). Quando a árvore binária não está vazia, existe um elemento chamado raiz, e os elementos restantes (se houver) são compostos de duas árvores binárias, chamadas de subárvore esquerda e subárvore direita de t, respectivamente.

A diferença fundamental entre uma árvore binária e uma árvore é:

As árvores binárias podem estar vazias, mas as árvores não podem estar vazias. Cada elemento em uma árvore binária possui exatamente duas subárvores (uma ou ambas podem estar vazias). Cada elemento da árvore pode ter várias subárvores. Em uma árvore binária, as subárvores de cada elemento são ordenadas, ou seja, podem ser distinguidas pelas subárvores esquerda e direita. As subárvores da árvore não são ordenadas. A figura abaixo mostra uma árvore binária representando uma expressão matemática. Há um total de 3 expressões matemáticas. Cada operador pode ter um ou dois operandos, o operando esquerdo é a subárvore esquerda do operador e o operando direito é a subárvore direita. Os nós folhas da árvore são constantes ou variáveis.

Características das árvores binárias Característica 1: O número de arestas de uma árvore binária contendo n (n>0) elementos é n-1.

Prove que cada elemento de uma árvore binária (exceto o nó raiz) possui exatamente um nó pai. Há apenas uma aresta entre o nó filho e o nó pai, então o número de arestas é n-1.

A altura ou profundidade de uma árvore binária refere-se ao número de níveis da árvore binária.

Característica 2: Se a altura de uma árvore binária for h, h≥0, então a árvore binária terá pelo menos h elementos e no máximo 2h−1 elementos.

Prova: Como cada nível deve ter pelo menos 1 elemento, o número de elementos é pelo menos h. Cada elemento tem no máximo 2 nós filhos, então os elementos do nó da i-ésima camada são no máximo 2i-1, i>0. Quando h=0, o número total de elementos é 0, que é 20−1. Quando h>0, o número total de elementos não excederá ∑hi=12i−1=2h−1.

Característica 3: A altura máxima de uma árvore binária contendo n elementos é n, e a altura mínima é ⌈log2(n+1)⌉.

Prova Como existe pelo menos um elemento em cada nível, a altura não pode exceder n. Pela propriedade 2, podemos saber que uma árvore binária com altura h possui no máximo 2h−1 elementos. Porque n≤2h−1, portanto h≥log2(n+1). Como h é um número inteiro, h≥⌈log2(n+1)⌉.

Quando uma árvore binária com altura h possui exatamente 2h−1 elementos, ela é chamada de árvore binária completa. A imagem abaixo é uma árvore binária completa com altura 4.

Suponha que os elementos em uma árvore binária completa de altura h sejam numerados de 1 a 2h−1 em ordem de cima para baixo e da esquerda para a direita, conforme mostrado na figura acima. Suponha que k elementos sejam excluídos da árvore binária completa e seu número seja 2h − i, 1≤i≤k. A árvore binária resultante é chamada de árvore binária completa. As três árvores binárias completas são mostradas na figura abaixo. Observe que uma árvore binária completa é um caso especial de uma árvore binária completa, e a profundidade de uma árvore binária completa com n elementos é ⌈log2(n+1)⌉.

Em uma árvore binária completa, um elemento tem uma correspondência muito boa com o número de seus filhos. A relação é dada na Propriedade 4 abaixo.

Característica 4: Suponha que o número de sequência de um elemento em uma árvore binária completa seja i, 1≤i≤n. Então é estabelecida a seguinte relação:

1. Quando i=1, o elemento é a raiz da árvore binária. Se i>1, o número do nó pai do elemento é ⌊i/2⌋.
2. Quando 2i>n, o elemento não possui subárvore esquerda, caso contrário, o número de sua subárvore esquerda é 2i.
3. Se 2i+1>n, o elemento não possui subárvore direita, caso contrário, o número de sua subárvore direita é 2i+1.

Árvore binária

1. Forma básica de árvore binária:

As árvores binárias também são definidas recursivamente e seus nós são divididos em subárvores esquerda e direita. Logicamente, as árvores binárias têm cinco formas básicas:

(1) Árvore binária vazia (2) Árvore binária com apenas um nó raiz (3) Apenas a subárvore certa (4) Apenas subárvore esquerda (5) Árvore binária completa

Nota: Embora as árvores binárias tenham muitas semelhanças com as árvores, as árvores binárias não são um caso especial de árvores.

2. Dois conceitos importantes:(1) Árvore binária completa - uma árvore binária em que apenas os graus dos nós dos dois níveis inferiores são inferiores a 2, e os nós do nível inferior estão concentrados em várias posições no lado esquerdo do nível; (2) Árvore binária completa - uma árvore binária em que cada nó, exceto os nós folha, tem cotilédones esquerdo e direito, e os nós folha estão todos na parte inferior.

3. Propriedades das árvores binárias (1) Em uma árvore binária, o número total de nós no nível i não excede 2^(i-1); (2) Uma árvore binária com profundidade h possui no máximo 2^h-1 nós (h>=1) e pelo menos h nós; (3) Para qualquer árvore binária, se o número de nós folha for N0 e o número total de nós com grau 2 for N2, Então N0=N2+1; (4) A profundidade de uma árvore binária completa com n nós é int(log2n)+1 (5) Se os nós de uma árvore binária completa com N nós forem armazenados de maneira sequencial, os nós terão o seguinte relacionamento: Se I for o número do nó, então se I<>1, então o número de seu nó pai será I/2; Se 2I<=N, então o número de seu filho esquerdo (ou seja, o nó raiz da subárvore esquerda) é 2I; se 2I>N, não há filho restante; Se 2I+1<=N, então o número do nó de seu filho direito é 2I+1; se 2I+1>N, não existe filho certo. (6) Dados N nós, h(N) diferentes árvores binárias podem ser formadas. h(N) é o enésimo termo do número Cattelan. h(n)=C(n,2*n)/(n+1).

árvore binária completa Uma árvore binária com profundidade k e 2 elevado à potência (k) - 1 nó. Recursos: O número de nós em cada nível é o número máximo de nós.

A definição de uma árvore binária completa: Uma árvore binária com profundidade k e n nós é chamada de árvore binária completa se e somente se cada um de seus nós corresponder a um nó numerado de 1 a n em uma árvore binária completa com profundidade k. Características: Os nós folha só podem aparecer nos dois níveis maiores; para qualquer nó, se o nível máximo de seus descendentes no ramo direito for l, então o nível máximo de seus descendentes no ramo esquerdo deverá ser l ou l+1. Árvore binária completa: uma árvore binária com profundidade k e 2 elevado à potência de 1 - 1 nós. Características: O número de nós em cada camada é o número máximo de nós. Uma árvore binária completa é definitivamente uma árvore binária completa. Uma árvore binária completa não é necessariamente uma árvore binária completa.

Mas a árvore de busca binária tem um problema muito problemático. Se dados aleatórios forem inseridos na árvore, o efeito de execução será muito bom, mas se dados ordenados ou de ordem reversa forem inseridos, a velocidade de execução da árvore de pesquisa binária se tornará muito lenta. Porque quando os valores inseridos são ordenados, a árvore binária fica desequilibrada e sua capacidade de localizar, inserir e excluir rapidamente itens de dados especificados é perdida.

Para resolver este problema, podemos usar multi-árvore.

Uma árvore 2-3-4 é uma árvore múltipla, com cada nó tendo até quatro nós filhos e três itens de dados. A árvore 2-3-4, assim como a árvore rubro-negra, também é uma árvore equilibrada. Sua eficiência é um pouco pior que a da árvore rubro-negra, mas é mais fácil de programar. Os significados de 2, 3 e 4 no nome da árvore 2-3-4 referem-se ao número de nós filhos que um nó pode conter. Existem três situações possíveis para nós não-folha:

Um nó com um item de dados sempre possui dois nós filhos; Um nó com dois itens de dados sempre possui três nós filhos; Um nó com três itens de dados sempre possui quatro pontos de byte.

Árvore de pesquisa binária, árvore 2-3-4, árvore vermelha e preta

Árvore binária

Referência; https://zh.wikipedia.org/wiki/二叉树 https://www.cnblogs.com/myjavascript/articles/4092746.html

Compartilhar

Como aprender estruturas de dados e algoritmos? Já compartilhei isso uma vez e recentemente vi um artigo que é muito consistente com meus pensamentos. Aqui está um resumo:

O básico que você precisa antes de responder a perguntas

1. Estruturas de dados comuns: listas vinculadas, árvores (como árvores binárias).
2. Ideias comuns de algoritmos: método ganancioso, método de divisão e conquista, método exaustivo, programação dinâmica, método de retrocesso.
3. Algoritmos de classificação comuns

Se você nem sabe essas coisas mais básicas, terá dificuldade em resolver as questões e terá relativamente poucas ideias. Pode-se dizer que para muitas questões você usará apenas métodos de força bruta, então você ainda precisa ser proficiente nessas coisas básicas antes de resolver as questões.

Você também deve ler livros e estudar sistematicamente.

Este último deve ser mais praticado. Durante o processo de prática, você deve aprender as excelentes soluções de outras pessoas. Não faça isso sozinho e tudo ficará bem. Você deve observar as implementações de outras pessoas e analisá-las cuidadosamente.

Além do leetcode, também existem nuke.com e os seguintes sites para escrever perguntas. 18 sites para praticar suas habilidades de programação https://blog.csdn.net/lyn167/article/details/52134859 [codificador superior] https://www.topcoder.com/ HackerEarth http://www.hackerearth.com/ Coderbyte https://coderbyte.com/ Projeto Euler: https://projecteuler.net/

Referência: Como aprendi estruturas de dados e algoritmos? ：https://mp.weixin.qq.com/s/Mo8xSmCnKrfIt3UpOLH6EQ O conteúdo do WeChat é frequentemente perdido, aqui está uma cópia: Link original: https://mp.weixin.qq.com/s/Mo8xSmCnKrfIt3UpOLH6EQ

O status das estruturas de dados e algoritmos é evidente para um programador. O artigo de hoje não está aqui para aconselhá-lo a aprender estruturas de dados e algoritmos, nem para dizer o quão importantes são as estruturas de dados e algoritmos.

Principalmente porque nos últimos dias os leitores me perguntaram como aprendi estruturas de dados e algoritmos, se existem atalhos, se para assistir vídeos ou ler livros, onde estudar questões, etc… E alguns deles são juniores e seniores, por isso estou ansioso e preocupado com vocês…

Então hoje vou compartilhar como costumo estudar.

O atalho para aprender algoritmos é responder a mais perguntas Para ser sincero, quando se trata de atalhos, acho que é preciso ter os pés no chão e praticar mais perguntas e responder mais perguntas.

Porém, se você é um novato, ou seja, ainda não aprendeu estruturas de dados comuns, como listas vinculadas, árvores e ideias comuns de algoritmos, como recursão, enumeração e programação dinâmica, então não recomendo que você estude as questões. Em vez disso, procure um livro para aprender primeiro e depois responda às perguntas.

Em outras palavras, se você quiser acessar um site como o leetcode para responder a perguntas, primeiro você deve ter uma certa base. Essas fundações incluem:

1. Estruturas de dados comuns: listas vinculadas, árvores (como árvores binárias).

2. Ideias comuns de algoritmos: método ganancioso, método de divisão e conquista, método exaustivo, programação dinâmica, método de retrocesso.

Os listados acima são os mais básicos. Ou seja, antes de responder às perguntas, você deve repassá-las e depois respondê-las. Se você nem sabe essas coisas mais básicas, terá dificuldade em responder às perguntas e terá relativamente poucas ideias.

Resumindo, não tenha pressa. Analise primeiro esses princípios básicos e tente entendê-los antes de responder às perguntas. Aprendi essas estruturas de dados e algoritmos básicos no segundo semestre do meu primeiro ano. Eu não assisti os vídeos. Eu os aprendi lendo livros. Os livros que li naquela época foram:

1. Análise de Algoritmos e Fundamentos de Análise: Este livro é relativamente simples e recomendado para iniciantes.

2. Estrutura de dados e análise de algoritmos - descrição da linguagem C: O código é escrito em C. Recomenda-se lê-lo.

3. Competição de Programação de Desafio (Segunda Edição): Este também é um livro muito bom, recomendado.

Para obter detalhes, você pode ler meu outro artigo, que apresenta estes livros: Livros sobre algoritmos e estrutura de dados e benefícios em vídeo

Para ser sincero, passei quase todo o meu tempo naquele semestre estudando estruturas de dados e algoritmos, mas houve pouquíssimas perguntas, apenas alguns exemplos do livro. Então, depois de passar por esses princípios básicos, ainda era muito difícil acessar alguns sites para responder perguntas.

Portanto, não espere pensar que será bom em responder perguntas depois de aprender essas ideias. Somente respondendo mais perguntas e praticando mais sua sensibilidade poderá ser melhorada.

Deixe-me falar sobre uma coluna muito popular há algum tempo - [A beleza das estruturas de dados e algoritmos]

Eu não comprei esta coluna. O que quero dizer é que se você comprar, deve ler e não desperdiçá-lo. Não pense que você se tornará mais incrível depois de aprender esta coluna. Se você apenas acompanhar o progresso do aprendizado desta coluna, não perderá tempo respondendo perguntas e fazendo exercícios práticos. Então posso garantir que você ainda será bom nisso depois de terminar os estudos.

Para resumir:

Não há atalho para melhorar estruturas de dados e algoritmos. O melhor atalho é responder a mais perguntas. No entanto, o pré-requisito para resolver as questões é que você primeiro aprenda algumas estruturas de dados básicas e ideias de algoritmos.

busca pela perfeição Como responder perguntas? Como lidar com um problema de algoritmo?

Acho que na hora de fazer perguntas você deve buscar a perfeição. Nunca termine uma pergunta, envie-a e passe-a e depois corra para a próxima.

Existe uma certa relação entre a melhoria das capacidades algorítmicas e o número de questões, mas não é uma relação linear. Em outras palavras, ao resolver um problema, você deve se esforçar para resolver vários problemas. Se você realmente não consegue pensar em outra maneira, pode ir e ver como os outros fazem isso. Não pense que é vergonhoso imitar o que os outros fazem.

Quando estou fazendo uma pergunta, quando vejo uma pergunta, meu primeiro pensamento pode ser resolvê-la de uma forma bem grosseira, porque muitas questões são fáceis de resolver pelo método da força bruta, mas a complexidade do tempo é muito alta. Depois disso, pensarei lentamente sobre isso e verei se existem outras maneiras de reduzir a complexidade do tempo ou do espaço. Finalmente, examinarei o que outros fizeram. É claro que nem todas as questões serão executadas desta forma.

Medir a qualidade de um problema de algoritmo nada mais é do que complexidade de tempo e complexidade de espaço. Portanto, se quisermos buscar a perfeição, devemos minimizar esses dois e fazer com que se complementem.

Deixe-me dar um exemplo:

Pergunta: Um sapo pode pular 1 ou 2 degraus de cada vez. De quantas maneiras o sapo pode subir uma escada de n níveis?

Analisei essa questão em capítulos anteriores. Se você não entende, pode ler o que escrevi antes: Recursão e Programação Dinâmica — Capítulo Básico 1

Método 1:: Recursão violenta

Esta questão não é difícil. Talvez você adote a seguinte abordagem:

público estático int resolver(int n){ se(n == 1 || n == 2){ retornar n; }senão se(n <= 0){ retornar 0; }outro{ retornar resolver(n-1) + resolver(n-2); } }

A complexidade de tempo desta abordagem é muito alta, exponencial. Mas se, por sorte, você passar após o envio e passar para a próxima pergunta, precisará pensar sobre isso com cuidado.

Método 2: Troque espaço por tempo

Para buscar a perfeição, podemos considerar a troca de espaço por tempo: se você pensar bem sobre essa questão, descobrirá que muitas delas se repetem. Portanto, você pode adotar a seguinte abordagem:

//Use um HashMap para salvar o estado calculado static Map<Integer,Integer> map = new HashMap(); público estático int resolver(int n){ se(n <= 0)retorna 0; senão se(n <= 2){ retornar n; }else{//Se foi calculado if(mapa.containsKey(n)){ retornar mapa.get(n); }outro{ int m = resolver(n-1) + resolver(n-2); mapa.put(n,m); retornar m; } } }

Desta forma, o tempo pode ser bastante reduzido. Em outras palavras, depois de resolver um problema e descobrir que a complexidade do tempo é muito alta, você pode considerar se existe um método melhor e se é possível trocar espaço por tempo.

Método 3: Sequência de Fibonacci

Na verdade, podemos diminuir ainda mais a complexidade do espaço e não precisamos de um HashMap para salvar o estado:

público estático int resolver(int n){ se(n <= 0) retornar 0; se(n <= 2){ retornar n; }int f1 = 0; int f2 = 1; soma interna = 0; for(int i = 1; i<= n; i++){ soma = f1 + f2; f1=f2; f2 = soma; } soma de retorno; }

Estou mostrando esta pergunta não para ensiná-lo a fazê-lo, mas para os seguintes propósitos:

1. Ao responder perguntas, devemos buscar a perfeição.

2. Não consigo pensar nesses métodos, o que devo fazer? Então você pode ver o que outros fizeram. Mais tarde, ao encontrar problemas semelhantes, você terá mais ideias e saberá em que direção pensar.

3. Você pode começar com violência simples para resolver um problema e otimizá-lo pouco a pouco, considerando a medição entre espaço e tempo.

Recomende alguns sites de perguntas e respostas Normalmente estudo questões no Leetcode e Niuke.com, e elas são muito boas. As perguntas não são muito difíceis.

Em Niuke.com, estudei principalmente a oferta Jianzhi, mas também existe um programa online chamado Leetcode, mas o número de perguntas nele é relativamente pequeno. Um lugar muito conveniente para resolver dúvidas no Niuke.com é a área de discussão. Haverá muitos grandes nomes compartilhando seus métodos de resolução de problemas, então não precisamos ir ao Baidu para encontrar a solução. Então, depois de terminar e você realmente não consegue pensar em mais nada, você pode facilmente ver como os outros fizeram isso.

Quanto ao leetcode, a maioria das perguntas tem respostas oficiais, e também é um bom site para esclarecer dúvidas. Você pode escolher um dos dois ou fazer ambos.

Claro, existem outros sites que abordam as questões, mas como não respondi aos outros sites, não sei como esclarecê-las.

Vamos falar sobre estrutura de dados Anteriormente, falei principalmente sobre como costumo aprender algoritmos. Em termos de métodos de estrutura de dados, acabei de listar que você deve aprender listas vinculadas e árvores (heaps binários), mas estas são as mais básicas e devem ser dominadas antes de responder às perguntas. Para estruturas de dados, listarei algumas das mais importantes:

1. Lista vinculada (como lista vinculada unidirecional, lista vinculada bidirecional).

2. Árvores (como árvores binárias, árvores equilibradas, árvores rubro-negras).

3. Gráfico (como vários algoritmos para caminhos mais curtos).

4. Fila, pilha, matriz.

Para estes, você deve implementá-lo sozinho. Você pode ler livros ou assistir a vídeos. Os novatos podem assistir aos vídeos primeiro, mas você pode assistir aos vídeos no estágio inicial. Depois disso, sugiro que você leia livros.

Já recomendei vídeos e livros antes: Livros sobre algoritmos e estrutura de dados e benefícios em vídeo

Por exemplo, para a árvore balanceada, você pode esquecê-la depois de um tempo seguindo o código do livro, mas isso não importa. Embora você tenha esquecido, se você o implementou com código antes e o compreendeu, quando o vir novamente, você se lembrará rapidamente e compreenderá a ideia rapidamente, e sua capacidade de abstração será melhorada inconscientemente. Mais tarde, se você aprender sobre árvores rubro-negras e outras estruturas de dados, você as aprenderá muito rapidamente.

O mais importante Faça, faça, faça. Diga coisas importantes três vezes.

Não ache um monte de recursos, faça um plano de estudos e deixe até um determinado dia para fazer…

Não faça isso, mas quando sua paixão surgir, faça-o imediatamente. Não deixe para um feriado ou algo assim. Muitas pessoas que pensam assim acabarão não fazendo nada.

Não sinta que há tanto para aprender e que não sabe por onde começar. Como eu disse acima, você pode aprender primeiro as mais básicas e depois estudar as questões. Estudar as questões é uma questão que exige persistência a longo prazo, um ano ou dois anos. No processo de resolução das questões, você pode intercalar o aprendizado de outras estruturas de dados.