java algorithms implementation Download - java algorithms implementation Download do código-fonte

java algorithms implementation

Código fonte JAVA

1.0.0

Baixar

Java: Algoritmos e Estrutura de Dados

Os algoritmos e estruturas de dados são implementados em Java.

Esta é uma coleção de algoritmos e estruturas de dados que implementei em minha vida acadêmica e profissional. O código não está otimizado, mas foi escrito para ser correto e legível. Os algoritmos e estruturas de dados são testados e, salvo indicação em contrário, considerados corretos.

Criado por Justin Wetherell

Para perguntas, use: http://groups.google.com/forum/#!forum/java-algorithms-implementation
Google: http://code.google.com/p/java-algorithms-implementation
Github: http://github.com/phishman3579/java-algorithms-implementation
LinkedIn: http://www.linkedin.com/in/phishman3579
E-mail: [email protected]
Twitter: http://twitter.com/phishman3579

Apoie-me com uma doação

O que foi implementado:

Índice

Estruturas de dados
Matemática
Números
Gráficos
Procurar
Sequências
Classifica
Funções de string

Estruturas de dados

Árvore AVL
Árvore B
Heap binário (apoiado por um array ou uma árvore)
Árvore de pesquisa binária
Compact Suffix Trie (apoiado por Patricia Trie)
Conjunto Disjunto
Árvore Fenwick {árvore binária indexada (BIT)}
Gráfico
- Não direcionado
- Dirigido (Dígrafo)
Teste mapeado de matriz de hash (HAMT)
Mapa Hash (matriz associativa)
Árvore de intervalo
Chave implícita
Árvore KD (árvore k-dimensional ou árvore kd)
Lista [apoiada por uma matriz ou lista vinculada]
LCP Array (Longest Common Prefix) [apoiado por um Suffix Array]
Matriz
Patrícia Trie
Quad-Tree (Ponto-Região ou MX-CIF)
Fila [apoiada por um array ou lista vinculada]
Radix Trie (matriz associativa) [apoiado por Patricia Trie]
Árvore Rubro-Negra
Árvore de segmento
Ignorar lista
Árvore de exibição
Pilha [apoiada por um array ou lista vinculada]
Matriz de sufixos
Árvore de sufixos (algoritmo de Ukkonen)
Sufixo Trie [apoiado por um Trie]
Árvore de pesquisa ternária
Armadilha
Árvore
Tree Map (matriz associativa) [apoiado por uma árvore AVL]
Tente
Mapa Trie (matriz associativa) [apoiado por um Trie]

Matemática

Distância
- Tchebyshev
- euclidiano
Divisão
- usando um laço
- usando recursão
- usando turnos e multiplicação
- usando apenas turnos
- usando logaritmo
Multiplicação
- usando um laço
- usando recursão
- usando apenas turnos
- usando logaritmos
- Transformada Rápida de Fourier
Exponenciação
- exponenciação recursiva
- exponenciação recursiva rápida
- exponenciação recursiva modular rápida
Primos
- é primo
- fatoração primária
- peneira de eratóstenes
- Teste de Miller-Rabin
- Co-primos (relativamente primos, mutuamente primos)
- Maior Divisor Comum
  - usando o algoritmo de Euclides
  - usando recursão
Permutações
- cordas
- números
Aritmética modular
- adicionar
- subtrair
- multiplicar
- dividir
- poder
Mochila
Ramer Douglas Peucker

Números

Inteiros
- para string binária
  - usando divisão e módulo
  - usando deslocamento para a direita e módulo
  - usando BigDecimal
  - usando dividir e dobrar
- é uma potência de 2
  - usando um laço
  - usando recursão
  - usando logaritmo
  - usando bits
- para inglês (por exemplo, 1 retornaria "um")
Longos
- para string binária
  - usando divisão e módulo
  - usando deslocamento para a direita e módulo
  - usando BigDecimal
Complexo
- adição
- subtração
- multiplicação
- valor absoluto
- valor polar

Gráficos

Encontre o(s) caminho(s) mais curto(s) em um gráfico a partir de um vértice inicial
- Algoritmo de Dijkstra (gráficos de peso não negativo)
- Algoritmo Bellman-Ford (gráficos de peso negativo e positivo)
Encontre a árvore geradora mínima
- Prim's (gráficos não direcionados)
- Kruskal (gráficos não direcionados)
Encontre o caminho mais curto de todos os pares
- Algoritmo de Johnsons (gráficos de peso negativo e positivo)
- Floyd-Warshall (gráficos de peso negativo e positivo)
Detecção de ciclo
- Primeira pesquisa em profundidade enquanto acompanha os vértices visitados
- Componentes Conectados
Classificação topológica
Algoritmo de localização de caminho A*
Fluxo máximo
- Push-Reetiquetar
Traversal do gráfico
- Primeira travessia em profundidade
- Amplitude da primeira travessia
Edmonds Karp
Correspondência
- Combinação Turbo
Menor ancestral comum na árvore

Procurar

Obtenha o índice de valor na matriz
- Linear
- Seleção rápida
- Binário [somente entrada de matriz classificada]
- Limite inferior [somente entrada de matriz classificada]
- Limite superior [somente entrada de matriz classificada]
- Binário otimizado (binário até um limite e depois linear) [somente entrada de matriz classificada]
- Interpolação [somente entrada de matriz classificada]

Sequências

Encontre a subsequência comum mais longa (programação dinâmica)
Encontre a subsequência crescente mais longa (programação dinâmica)
Encontre o número de vezes que uma subsequência ocorre em uma sequência (programação dinâmica)
Encontre o i-ésimo elemento em uma sequência de Fibonacci
- usando um laço
- usando recursão
- usando multiplicação de matrizes
- usando a fórmula de Binet
Encontre o total de todos os elementos em uma sequência (progressão aritmética)
- usando um laço
- usando números triangulares
Maior soma de submatriz contígua (algoritmo de Kadane)
Subsequência palindrômica mais longa (programação dinâmica)

Classifica

Classificação da bandeira americana
Classificação por bolha
Classificação por contagem (somente números inteiros)
Classificação de pilha
Classificação de inserção
Mesclar classificação
Classificação rápida
Classificação Radix (somente números inteiros)
Tipo de Shell

Funções de string

Reverter caracteres em uma string
- usando armazenamento adicional (uma String ou StringBuilder)
- usando swaps no local
- usando XOR no local
Reverter palavras em uma string
- usando trocas de caracteres e armazenamento adicional (um StringBuilder)
- usando StringTokenizer e adicional (uma String)
- usando o método split() e armazenamento adicional (um StringBuilder e String[])
- usando swaps no local
É Palíndromo
- usando armazenamento adicional (um StringBuilder)
- usando comparações de elementos simétricos no local
Subconjuntos de caracteres em uma String
Editar (Levenshtein) Distância de duas Strings (Recursiva, Iterativa)