Structures de données et algorithmes Java : guide du débutant

Les structures de données et les algorithmes en Java fournissent une prise en charge de base pour des programmes efficaces et évolutifs : 1. Les structures de données couramment utilisées incluent des tableaux, des listes chaînées, des piles, des files d'attente, des arbres et des graphiques ; 2. Les algorithmes sont des séquences d'étapes organisées pour résoudre des problèmes spécifiques, notamment ; tri, recherche, programmation dynamique, retour en arrière et algorithmes gloutons ; 3. Les structures de données et les algorithmes peuvent être utilisés pour résoudre des problèmes en combat réel, tels que la recherche du sous-tableau de la somme spécifiée via une table de hachage et le calcul de la somme des préfixes, et le processus spécifique est reflété dans le code.

Structures de données et algorithmes Java : guide du débutant

Les structures de données et les algorithmes sont fondamentaux dans le domaine de l'informatique et sont essentiels pour écrire des programmes efficaces et évolutifs. Java, en tant que langage, fournit un large éventail de structures de données qui aident les programmeurs à stocker et organiser efficacement les données. Les algorithmes sont des méthodes de traitement et de manipulation de ces données pour résoudre des problèmes spécifiques.

Structures de données

Plusieurs structures de données courantes en Java incluent :

• Array : Stocke une séquence ordonnée d'éléments du même type.
• Liste liée : Stocke une collection d'éléments, où chaque élément pointe vers l'élément suivant.
• Stack : Une structure de données qui suit le principe du dernier entré, premier sorti (LIFO).
• Queue : Une structure de données qui suit le principe du premier entré, premier sorti (FIFO).
• Arbre : Une structure hiérarchique où chaque nœud peut avoir plusieurs nœuds enfants.
• Graphique : Une collection de nœuds et d'arêtes connectés, utilisés pour représenter des relations complexes.

Algorithme

Un algorithme est une séquence méthodique d'étapes conçues pour résoudre un problème spécifique. Les algorithmes courants en Java incluent :

• Algorithme de tri : Trier les éléments par ordre croissant ou décroissant.
• Algorithme de recherche : Rechercher des éléments dans une structure de données.
• Algorithme de programmation dynamique : Décomposez les gros problèmes en problèmes plus petits, puis résolvez-les un par un.
• Algorithme de Backtracking : Explorez systématiquement toutes les possibilités pour trouver la meilleure solution.
• Algorithme gourmand : Faites un choix local optimal à chaque étape.

Cas pratique

Voyons à travers un exemple comment utiliser des structures de données et des algorithmes pour résoudre de vrais problèmes en Java :

Problème : Étant donné un tableau d'entiers, découvrir s'il existe un sous-tableau dont et est la valeur cible.

Solution :

import java.util.HashMap;

public class SubarraySum {

    public static boolean subarraySum(int[] nums, int target) {
        // 哈希表存储前缀和和出现次数
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);

        int sum = 0;
        // 遍历数组
        for (int num : nums) {
            // 更新前缀和
            sum += num;
            // 检查是否有前缀和为 (sum - target)
            if (map.containsKey(sum - target)) {
                return true;
            }
            // 将前缀和添加到哈希表中
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }

        return false;
    }

    public static void main(String[] args) {
        int[] nums = {1, 4, 20, 3, 10, 5};
        int target = 33;

        boolean result = subarraySum(nums, target);
        System.out.println("是否存在符合要求的子数组：" + result);
    }
}

Procédure :

• Utilisez une table de hachage pour stocker le mappage des préfixes et des occurrences.
• Parcourez le tableau et mettez à jour la somme actuelle des préfixes.
• Chaque fois que la somme des préfixes est mise à jour, vérifiez s'il existe une somme de préfixes de (sum - target), et si c'est le cas, trouvez le sous-tableau correspondant. (sum - target)，如果有，则找到匹配的子数组。
• 将更新后的前缀和添加到哈希表中。
• 遍历数组后，如果哈希表中不包含任何与 (sum - target)
Ajoutez la somme de préfixe mise à jour à la table de hachage.

🎜Après avoir parcouru le tableau, si la table de hachage ne contient aucune somme de préfixe correspondant à (sum - target), alors il n'y a pas de sous-tableau correspondant. 🎜🎜

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!