Caractéristiques des talbeaux

Un tableau stocke des éléments de même type dans des emplacements mémoire contigus. L'accès se fait via un indice entier commençant à 0. Les éléments ne peuvent pas être supprimés physiquement ; on ne peut que les écraser.

Recherche binaire (LeetCode 704)

Rechercher une valeur cible dans un tableau trié en temps O(log n).

function binarySearch(nums, target) {
    let low = 0, high = nums.length;
    while (low < high) {
        const mid = low + ((high - low) >> 1);
        if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return nums[low] === target ? low : -1;
}

Vérifier un carré parfait (LeetCode 367)

Déterminer si un entier positif est un carré parfait sans utiliser Math.sqrt.

function isPerfectSquare(num) {
    let lo = 1, hi = num;
    while (lo <= hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        const sq = mid * mid;
        if (sq === num) return true;
        if (sq < num) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

Racine carrée entière (LeetCode 69)

Calculer la partie entière de la racine carrée d’un entier non négatif.

function integerSqrt(x) {
    if (x < 2) return x;
    let lo = 1, hi = x;
    while (lo <= hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (mid <= x / mid && (mid + 1) > x / (mid + 1)) {
            return mid;
        } else if (mid <= x / mid) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
}

Positions extrêmes d’une cible (LeetCode 34)

Trouver les indices de la première et dernière occurrence d’une valeur dans un tableau trié.

function findRange(nums, target) {
    const findBound = (isFirst) => {
        let idx = -1, lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            const mid = lo + ((hi - lo) >> 1);
            if (nums[mid] === target) {
                idx = mid;
                if (isFirst) hi = mid - 1;
                else lo = mid + 1;
            } else if (nums[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return idx;
    };
    const first = findBound(true);
    if (first === -1) return [-1, -1];
    const last = findBound(false);
    return [first, last];
}

Position d’insertion (LeetCode 35)

Trouver l’indice où insérer une valeur pour maintenir l’ordre croissant.

function searchInsertPos(arr, val) {
    let lo = 0, hi = arr.length;
    while (lo < hi) {
        const mid = lo + ((hi - lo) >> 1);
        if (arr[mid] < val) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

Suppression in situ (LeetCode 27)

Supprimer toutes les occurrences d’une valeur donnée et retourner la nouvelle longueur.

function removeValue(arr, val) {
    let writeIdx = 0;
    for (let readIdx = 0; readIdx < arr.length; readIdx++) {
        if (arr[readIdx] !== val) {
            arr[writeIdx++] = arr[readIdx];
        }
    }
    return writeIdx;
}

Carrés triés (LeetCode 977)

Retourner les carrés des éléments d’un tableau trié non décroissant, également triés.

function sortedSquared(arr) {
    const n = arr.length;
    const result = new Array(n);
    let left = 0, right = n - 1, pos = n - 1;
    while (left <= right) {
        const leftSq = arr[left] * arr[left];
        const rightSq = arr[right] * arr[right];
        if (leftSq > rightSq) {
            result[pos--] = leftSq;
            left++;
        } else {
            result[pos--] = rightSq;
            right--;
        }
    }
    return result;
}

Sous-tableau minimal (LeetCode 209)

Trouver la longueur minimale d’un sous-tableau contigu dont la somme est ≥ target.

function minSubArrayLen(target, nums) {
    let minLength = Infinity;
    let windowSum = 0, left = 0;
    for (let right = 0; right < nums.length; right++) {
        windowSum += nums[right];
        while (windowSum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            windowSum -= nums[left++];
        }
    }
    return minLength === Infinity ? 0 : minLength;
}

Matrice spirale (LeetCode 59)

Générer une matrice n × n remplie de 1 à n² en ordre spiral.

function generateSpiralMatrix(n) {
    const matrix = Array(n).fill().map(() => Array(n).fill(0));
    let value = 1;
    let top = 0, bottom = n - 1, left = 0, right = n - 1;
    while (top <= bottom && left <= right) {
        for (let col = left; col <= right; col++) matrix[top][col] = value++;
        top++;
        for (let row = top; row <= bottom; row++) matrix[row][right] = value++;
        right--;
        if (top <= bottom) {
            for (let col = right; col >= left; col--) matrix[bottom][col] = value++;
            bottom--;
        }
        if (left <= right) {
            for (let row = bottom; row >= top; row--) matrix[row][left] = value++;
            left++;
        }
    }
    return matrix;
}