Dia 2 - Progresso não é linear

Apesar da diferença em relação as datas, o que importa é fazer 100 dias - não necessariamente consecutivos - do desafio. Dessa vez vou focar em um guia de reconhecimento de padrões de problemas do leetcode pelo canal Bitflip

Dica 1 - olhe as restrições (constraints):

Antes de resolver qualquer problema, é recomendado checar as restrições primeiro. Por quê? Bom, você consegue definir a forma como vai atacar o problema. Por exemplo se n for um valor pequeno como 1 <= n <= 20 quer dizer que da pra usar alguns métodos exponenciais O(n^2): - força bruta - backtracking - recursão

Agora se n for um valor grande como 1 <= n <= 10^5 então você precisa de algo mais eficiente, pelo menos O(n): - soluções gulosas - 2 ponteiros - Pilha - dp (programação dinâmica)

Agora se o valor for enorme como 1 <= b <= 10^8, tem que ser O(n log n): - Algum algoritmo matemático - busca binária

Dica 2 - Analise o formato da entrada:

Se o problema te dar que a entrada como uma Árvore, Árvore Binária, ou uma Árvore de Busca Binária (BST). Muito provavelmente a solução vai estar no uso de algoritmos como BFS ou DFS: - Se precisa explorar o caminho completo DFS, ou se falar se é pre-ordem, pós-ordem ou na ordem. - Se precisa checar todos os galhos BFS

Se for um gráfo também entra nesse caso. Usando além do BFS e DFS também o Union Find. E nesse caso usa o UF quando o problema fala de componentes conectados, ou número de grupos.

Se for um vetor ordenado, então usa-se: - 2 ponteiros - Pesquisa binária - Solução gulosas

Agora se for só um vetor não ordenado ou um número, tem que procurar por palavras chaves e pelo contexto do problema.

Dica 3 - Analise o formato da saida:

Tão importante quanto a entrada, é a saída. Por exemplo se o retorno for uma lista de listas - essencialmente uma matriz de informação, ex.: todas as combinações, todos os caminhos, etc - é recomendado uma solução de Backtracking.

Se a saída for um único valor, como o valor máximo, custo mínimo, número de possibilidades. É utilizado ou DP ou solução gulosa.

Se for um vetor modificado, ou uma string - um vetor de char - a solução é 99% 2 ponteiros.

Se for uma lista ordenada, ai obviamente a solução é ordenação (bubble, quick, etc) ou topológica.

Dica 4 - Palavras chave:

Bom o vídeo já disponibilizou uma lista extensa então vou só colar direto aqui:

Aqui está o texto a partir do Passo 4: Reconhecimento de Padrões por Palavra-Chave do documento:

Dynamic Programming Keywords:

• “Number of ways”
• “Maximum/minimum” + “sum/profit/cost”
• “Can you reach”
• “Longest/shortest subsequence”
• “Optimal” or “best”

Two Pointers Keywords:

• “Palindrome”
• “Sorted array”
• “Target sum”
• “Remove duplicates”

Heap Keywords:

• “K largest” or “K smallest”
• “Top K elements”
• “Median”
• “Priority”

Stack Keywords:

• “Parentheses” or “brackets”
• “Valid expression”
• “Nested structure”
• “Undo operations”

Monotonic Stack Keywords:

• “Next greater element”
• “Next smaller element”

HashMap Keywords:

• “Count frequency”
• “Find duplicates”
• “Anagram”

Trie Keywords:

• “Word search”
• “Word prefixes”

Greedy Keywords:

• “Minimum operations”

Union Find Keywords:

• “Connected components”
• “Number of groups”

Binary Search Keywords:

• “Kth element”
• “Search in sorted”
• “Minimize maximum”
• “First/last occurrence”

Bit Manipulation:

• “XOR” operations
• “Single number” problems
• “Power of 2”

Math/Geometry:

• “Greatest/Least Common Denominator”
• “Prime numbers”
• “Angle calculations”
• “Coordinate”

Game Theory:

• “Optimal strategy”
• “Win/lose scenarios”
• “Minimax”

Sliding Window:

• “Substring” with conditions
• “Subarray” with fixed/variable size
• “Maximum/minimum window”
• “Contains all”

Com isso em mente agora posso começar atacando os problemas mais comuns tentando desenvolver a minha intuição.