java algorithms implementation Télécharger - java algorithms implementation Téléchargement du code source

java algorithms implementation

Code source JAVA

1.0.0

Télécharger

Java : Algorithmes et Structure des Données

Les algorithmes et les structures de données sont implémentés en Java.

Il s'agit d'un ensemble d'algorithmes et de structures de données que j'ai mis en œuvre dans ma vie universitaire et professionnelle. Le code n'est pas optimisé mais est écrit pour être correct et lisible. Les algorithmes et les structures de données sont testés et, sauf indication contraire, considérés comme corrects.

Créé par Justin Wetherell

Pour toute question, utilisez : 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
Courriel : [email protected]
Twitter : http://twitter.com/phishman3579

Soutenez-moi avec un don

Ce qui a été mis en œuvre :

Table des matières

Structures de données
Mathématiques
Nombres
Graphiques
Recherche
Séquences
Tris
Fonctions de chaîne

Structures de données

Arbre AVL
Arbre B
Tas binaire (soutenu par un tableau ou un arbre)
Arbre de recherche binaire
Compact Suffix Trie (soutenu par Patricia Trie)
Ensemble disjoint
Arbre Fenwick {Arbre indexé binaire (BIT)}
Graphique
- Non dirigé
- Réalisé (Digraphe)
Trie mappé par tableau de hachage (HAMT)
Carte de hachage (tableau associatif)
Arbre d'intervalle
Treap clé implicite
Arbre KD (arbre à k dimensions ou arbre kd)
Liste [soutenue par un tableau ou une liste chaînée]
Tableau LCP (préfixe commun le plus long) [soutenu par un tableau de suffixes]
Matrice
Patricia Trié
Quad-Tree (Point-Region ou MX-CIF)
File d'attente [soutenue par un tableau ou une liste chaînée]
Radix Trie (tableau associatif) [soutenu par Patricia Trie]
Arbre rouge-noir
Arbre de segments
Ignorer la liste
Arbre évasé
Pile [soutenu par un tableau ou une liste chaînée]
Tableau de suffixes
Arbre de suffixes (algorithme d'Ukkonen)
Suffixe Trie [soutenu par un Trie]
Arbre de recherche ternaire
Treap
Arbre
Tree Map (tableau associatif) [soutenu par un arbre AVL]
Essayer
Trie Map (tableau associatif) [soutenu par un Trie]

Mathématiques

Distance
- Tchebychev
- euclidien
Division
- en utilisant une boucle
- utiliser la récursivité
- utiliser les décalages et la multiplication
- en utilisant uniquement les équipes
- en utilisant le logarithme
Multiplication
- en utilisant une boucle
- utiliser la récursivité
- en utilisant uniquement les équipes
- utiliser des logarithmes
- Transformée de Fourier rapide
Exponentiation
- exponentiation récursive
- exponentiation récursive rapide
- exponentiation récursive modulaire rapide
Primes
- est premier
- factorisation première
- tamis d'ératosthène
- Test de Miller-Rabin
- Co-Primes (relativement premiers, mutuellement premiers)
- Plus grand diviseur commun
  - en utilisant l'algorithme d'Euclide
  - utiliser la récursivité
Permutations
- cordes
- Nombres
Arithmétique modulaire
- ajouter
- soustraire
- multiplier
- diviser
- pouvoir
Sac à dos
Ramer Douglas Peucker

Nombres

Entiers
- en chaîne binaire
  - en utilisant la division et le module
  - en utilisant le décalage à droite et le module
  - en utilisant BigDecimal
  - en utilisant diviser et doubler
- est une puissance de 2
  - en utilisant une boucle
  - utiliser la récursivité
  - en utilisant le logarithme
  - utiliser des bits
- en anglais (par exemple, 1 renverrait "one")
Longues
- en chaîne binaire
  - en utilisant la division et le module
  - en utilisant le décalage à droite et le module
  - en utilisant BigDecimal
Complexe
- ajout
- soustraction
- multiplication
- valeur absolue
- valeur polaire

Graphiques

Rechercher le(s) chemin(s) le plus court(s) dans un graphique à partir d'un sommet de départ
- Algorithme de Dijkstra (graphiques de poids non négatifs)
- Algorithme Bellman-Ford (graphiques de poids négatifs et positifs)
Trouver l'arbre couvrant minimum
- Prim's (graphiques non orientés)
- Kruskal (graphiques non orientés)
Trouver le chemin le plus court de toutes les paires
- Algorithme de Johnsons (graphiques de poids négatifs et positifs)
- Floyd-Warshall (graphiques de poids négatifs et positifs)
Détection de cycles
- Recherche en profondeur tout en gardant une trace des sommets visités
- Composants connectés
Tri topologique
Un* algorithme de recherche de chemin
Débit maximal
- Push-Relabel
Traversée du graphique
- Première traversée en profondeur
- Largeur première traversée
Edmonds Karp
Correspondance
- Correspondance Turbo
Ancêtre commun le plus bas de l'arbre

Recherche

Obtenir l'index de la valeur dans le tableau
- Linéaire
- Sélection rapide
- Binaire [entrée de tableau trié uniquement]
- Limite inférieure [entrée de tableau trié uniquement]
- Limite supérieure [entrée de tableau trié uniquement]
- Binaire optimisé (binaire jusqu'à un seuil puis linéaire) [entrée tableau trié uniquement]
- Interpolation [entrée de tableau trié uniquement]

Séquences

Trouver la sous-séquence commune la plus longue (programmation dynamique)
Trouver la sous-séquence croissante la plus longue (programmation dynamique)
Trouver le nombre de fois qu'une sous-séquence apparaît dans une séquence (programmation dynamique)
Trouver le i-ième élément dans une séquence de Fibonacci
- en utilisant une boucle
- utiliser la récursivité
- utiliser la multiplication matricielle
- en utilisant la formule de Binet
Trouver le total de tous les éléments d'une séquence (progression arithmétique)
- en utilisant une boucle
- en utilisant des nombres triangulaires
La plus grande somme de sous-tableaux contigus (algorithme de Kadane)
Sous-séquence palindromique la plus longue (programmation dynamique)

Tris

Tri du drapeau américain
Tri à bulles
Tri par comptage (entiers uniquement)
Tri en tas
Tri par insertion
Fusionner le tri
Tri rapide
Tri par base (entiers uniquement)
Tri de Shell

Fonctions de chaîne

Inverser les caractères dans une chaîne
- en utilisant un stockage supplémentaire (un String ou un StringBuilder)
- utiliser des échanges sur place
- utiliser XOR sur place
Inverser les mots dans une chaîne
- en utilisant des échanges de caractères et un stockage supplémentaire (un StringBuilder)
- en utilisant StringTokenizer et supplémentaire (une chaîne)
- en utilisant la méthode split() et un stockage supplémentaire (un StringBuilder et String[])
- utiliser des échanges sur place
est le palindrome
- en utilisant un stockage supplémentaire (un StringBuilder)
- l'utilisation d'éléments symétriques sur place compare
Sous-ensembles de caractères dans une chaîne
Modifier (Levenshtein) Distance de deux chaînes (récursive, itérative)