Tableaux

Recherche binaire

Étant donné un tableau trié en ordre croissant et une valeur cible, implémentez une fonction de recherche avec une complexité O(log n) retournant l'index de la cible ou -1.

Deux approches selon la définition de l'intervalle :

• Intervalle [gauche, droite) : right = longueur du tableau
• Intervalle [gauche, droite] : right = longueur - 1

// Approche [gauche, droite)
class Solution {
    public int search(int[] nums, int target) {
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int debut = 0;
        int fin = nums.length;
        while (debut < fin) {
            int milieu = debut + ((fin - debut) >> 1);
            if (nums[milieu] > target) {
                fin = milieu;
            } else if (nums[milieu] < target) {
                debut = milieu + 1;
            } else {
                return milieu;
            }
        }
        return -1;
    }
}

// Approche [gauche, droite]
class Solution {
    public int search(int[] nums, int target) {
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int debut = 0;
        int fin = nums.length - 1;
        while (debut <= fin) {
            int milieu = debut + ((fin - debut) >> 1);
            if (nums[milieu] > target) {
                fin = milieu - 1;
            } else if (nums[milieu] < target) {
                debut = milieu + 1;
            } else {
                return milieu;
            }
        }
        return -1;
    }
}

Points d'attention

• Avec l'intervalle [gauche, droite), l'affectation de fin est milieu et non milieu - 1
• L'opérateur de décalage de bits a une priorité inférieure à l'addition : debut + ((fin - debut) >> 1) nécessite les parenthèses

Suppression d'éléments en place

Supprimez en place toutes les occurrences d'une valeur donnée dans le tableau et retournez le nombre d'éléments restants.

Deux stratégies : méthode à double pointeur et méthode brute.

// Double pointeur
class Solution {
    public int removeElement(int[] nums, int val) {
        int lent = 0;
        for (int rapide = 0; rapide < nums.length; rapide++) {
            if (nums[rapide] != val) {
                nums[lent++] = nums[rapide];
            }
        }
        return lent;
    }
}

// Méthode brute
class Solution {
    public int removeElement(int[] nums, int val) {
        int taille = nums.length;
        for (int i = 0; i < taille; i++) {
            if (nums[i] == val) {
                for (int k = i + 1; k < taille; k++) {
                    nums[k - 1] = nums[k];
                }
                i--;
                taille--;
            }
        }
        return taille;
    }
}

Points d'attention

• C'est le pointeur rapide qui vérifie la différence avec val
• Pensez à décrémenter i et taille dans la méthode brute

Carrés triés d'un tableau ordonné

Retournez les carrés des éléments d'un tableau trié en ordre non décroissant, également triés en ordre non décroissant.

// Double pointeur
class Solution {
    public int[] sortedSquares(int[] nums) {
        int g = 0;
        int d = nums.length - 1;
        int[] resultat = new int[nums.length];
        int pos = nums.length - 1;
        while (g <= d) {
            int carreG = nums[g] * nums[g];
            int carreD = nums[d] * nums[d];
            if (carreG > carreD) {
                resultat[pos--] = carreG;
                g++;
            } else {
                resultat[pos--] = carreD;
                d--;
            }
        }
        return resultat;
    }
}

// Approche directe
class Solution {
    public int[] sortedSquares(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] *= nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
}

Points d'attention

• Utilisez un index séparé pour suivre la position dans le tableau résultat

Plus petit sous-tableau de somme minimale

Trouvez le sous-tableau continu de longueur minimale dont la somme est supérieure ou égale à une valeur cible.

// Fenêtre glissante
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int meilleur = Integer.MAX_VALUE;
        int sommeCourante = 0;
        int debut = 0;
        for (int fin = 0; fin < nums.length; fin++) {
            sommeCourante += nums[fin];
            while (sommeCourante >= target) {
                int longueur = fin - debut + 1;
                meilleur = Math.min(meilleur, longueur);
                sommeCourante -= nums[debut++];
            }
        }
        return meilleur == Integer.MAX_VALUE ? 0 : meilleur;
    }
}

// Méthode brute
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int meilleur = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int somme = 0;
            for (int j = i; j < nums.length; j++) {
                somme += nums[j];
                if (somme >= target) {
                    meilleur = Math.min(meilleur, j - i + 1);
                    break;
                }
            }
        }
        return meilleur == Integer.MAX_VALUE ? 0 : meilleur;
    }
}

Points d'attention

• Pour chercher un minimum, initialisez avec Integer.MAX_VALUE
• Pour chercher un maximum, initialisez avec Integer.MIN_VALUE

Matrice spirale

Générez une matrice n×n contenant les entiers de 1 à n² disposés en spirale horaire.

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrice = new int[n][n];
        int x = 0, y = 0;
        int tour = 1;
        int compteur = 1;
        while (tour <= n / 2) {
            for (int col = y; col < n - tour; col++) {
                matrice[x][col] = compteur++;
            }
            for (int lig = x; lig < n - tour; lig++) {
                matrice[lig][n - tour] = compteur++;
            }
            for (int col = n - tour; col > y; col--) {
                matrice[n - tour][col] = compteur++;
            }
            for (int lig = n - tour; lig > x; lig--) {
                matrice[lig][y] = compteur++;
            }
            x++;
            y++;
            tour++;
        }
        if (n % 2 == 1) {
            matrice[x][y] = compteur;
        }
        return matrice;
    }
}

Points d'attention

• Les coordonnées de départ et les bornes des quatre boucles doivent être précises
• Si n est impair, il faut assigner manuellement la case centrale

Somme d'intervalle (tableau de préfixes)

Calculez la somme des éléments d'un tableau sur différents intervalles spécifiés.

// Préfixe
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] tab = new int[n];
        tab[0] = sc.nextInt();
        for (int i = 1; i < n; i++) {
            tab[i] = sc.nextInt() + tab[i - 1];
        }
        while (sc.hasNextInt()) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            System.out.println(a == 0 ? tab[b] : tab[b] - tab[a - 1]);
        }
    }
}

// Méthode directe (risque de timeout)
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] tab = new int[n];
        for (int i = 0; i < n; i++) {
            tab[i] = sc.nextInt();
        }
        while (sc.hasNextInt()) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int total = 0;
            for (int i = a; i <= b; i++) {
                total += tab[i];
            }
            System.out.println(total);
        }
    }
}

Points d'attention

• La méthode brute peut provoquer un timeout
• Attention au cas où la borne inférieure de l'intervalle est 0

Acquisition de terrain (somme préfixée bidimensionnelle)

Divisez une grille n×m en deux régions (horizontalement ou verticalement) de manière à minimiser la différence de valeur totale entre les deux parties.

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] grille = new int[n][m];
        int total = 0;
        int meilleur = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grille[i][j] = sc.nextInt();
                total += grille[i][j];
            }
        }

        int cumulLigne = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cumulLigne += grille[i][j];
            }
            meilleur = Math.min(meilleur, Math.abs(total - 2 * cumulLigne));
        }

        int cumulCol = 0;
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                cumulCol += grille[i][j];
            }
            meilleur = Math.min(meilleur, Math.abs(total - 2 * cumulCol));
        }

        System.out.println(meilleur);
    }
}

Points d'attention

• Pour le cumul vertical, il suffit d'inverser l'ordre des indices i et j

Listes chaînées

Suppression d'élémants d'une liste chaînée

Supprimez tous les nœuds dont la valeur égale une valeur donnée.

// Sans nœud sentinelle
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        while (head != null && head.val == val) {
            head = head.next;
        }
        ListNode courant = head;
        while (courant != null && courant.next != null) {
            if (courant.next.val == val) {
                courant.next = courant.next.next;
            } else {
                courant = courant.next;
            }
        }
        return head;
    }
}

// Avec nœud sentinelle
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode sentinelle = new ListNode();
        sentinelle.next = head;
        ListNode courant = sentinelle;
        while (courant.next != null) {
            if (courant.next.val == val) {
                courant.next = courant.next.next;
            } else {
                courant = courant.next;
            }
        }
        return sentinelle.next;
    }
}

Points d'attention

• Sans sentinelle, il faut déplacer la tête jusqu'à un nœud non concerné
• Avec sentinelle, retournez sentinelle.next

Implémentation d'une liste chaînée

// Liste simplement chaînée
class MyLinkedList {
    class Noeud {
        int val;
        Noeud suivant;
        Noeud(int val) {
            this.val = val;
        }
    }

    private int taille;
    private Noeud tete;

    public MyLinkedList() {
        taille = 0;
        tete = new Noeud(0);
    }

    public int get(int index) {
        if (index < 0 || index >= taille) return -1;
        Noeud cur = tete;
        for (int i = 0; i <= index; i++) {
            cur = cur.suivant;
        }
        return cur.val;
    }

    public void addAtHead(int val) {
        Noeud nouveau = new Noeud(val);
        nouveau.suivant = tete.suivant;
        tete.suivant = nouveau;
        taille++;
    }

    public void addAtTail(int val) {
        Noeud cur = tete;
        while (cur.suivant != null) {
            cur = cur.suivant;
        }
        cur.suivant = new Noeud(val);
        taille++;
    }

    public void addAtIndex(int index, int val) {
        if (index < 0 || index > taille) return;
        Noeud cur = tete;
        for (int i = 0; i < index; i++) {
            cur = cur.suivant;
        }
        Noeud nouveau = new Noeud(val);
        nouveau.suivant = cur.suivant;
        cur.suivant = nouveau;
        taille++;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= taille) return;
        Noeud cur = tete;
        for (int i = 0; i < index; i++) {
            cur = cur.suivant;
        }
        cur.suivant = cur.suivant.suivant;
        taille--;
    }
}

Points d'attention

• Ne pas oublier d'incrémenter ou décrémenter la taille
• get et deleteAtIndex utilisent index >= taille car il n'y a pas de nœud à l'index taille
• addAtIndex permet index == taille car on peut ajouter en fin

Inversion de liste chaînée

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode precedent = null;
        ListNode actuel = head;
        while (actuel != null) {
            ListNode temp = actuel.next;
            actuel.next = precedent;
            precedent = actuel;
            actuel = temp;
        }
        return precedent;
    }
}

Points d'attention

• Trois références sont nécessaires : précédent, actuel et temporaire

Échange par paires de nœuds

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode sentinelle = new ListNode(-1);
        sentinelle.next = head;
        ListNode cur = sentinelle;
        while (cur.next != null && cur.next.next != null) {
            ListNode p1 = cur.next;
            ListNode p2 = cur.next.next;
            ListNode p3 = p2.next;
            cur.next = p2;
            p2.next = p1;
            p1.next = p3;
            cur = p1;
        }
        return sentinelle.next;
    }
}

Points d'attention

• Il est fortement recommandé de dessiner les pointeurs pour éviter les confusions

Suppression du nœud en n-ième position depuis la fin

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sentinelle = new ListNode(-1);
        sentinelle.next = head;
        ListNode lent = sentinelle;
        ListNode rapide = sentinelle;
        for (int i = 0; i <= n; i++) {
            rapide = rapide.next;
        }
        while (rapide != null) {
            lent = lent.next;
            rapide = rapide.next;
        }
        lent.next = lent.next.next;
        return sentinelle.next;
    }
}

Points d'attention

• Si le pointeur rapide avance de n+1 pas, la condition de boucle est rapide != null
• Si le pointeur rapide avance de n pas, la condition devient rapide.next != null

Intersection de deux listes chaînées

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2 = headB;
        while (p1 != p2) {
            p1 = (p1 == null) ? headB : p1.next;
            p2 = (p2 == null) ? headA : p2.next;
        }
        return p1;
    }
}

Points d'attention

• Les deux pointeurs finiront par se rencontrer, soit à l'intersection, soit à null simultanément

Détection du cycle dans une liste chaînée

Identifiez le nœud d'entrée du cycle dans une liste chaînée.

Démonstration : si les pointeurs rapide et lent se rencontrent, en posant x la distance avant le cycle, y la distance jusqu'au point de rencontre et z la distance du point de rencontre à l'entrée du cycle, on obtient :

2(x + y) = x + y + n(y + z) → x = z + (n-1)(y + z)

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode lent = head;
        ListNode rapide = head;
        while (rapide != null && rapide.next != null) {
            lent = lent.next;
            rapide = rapide.next.next;
            if (lent == rapide) break;
        }
        if (rapide == null || rapide.next == null) return null;
        lent = head;
        while (lent != rapide) {
            lent = lent.next;
            rapide = rapide.next;
        }
        return lent;
    }
}

Points d'attention

• Il faut vérifier à la fois rapide != null et rapide.next != null car le pointeur rapide saute deux nœuds à la fois