Aller au contenu principal

LeetCode 8

Quentin Fortier
Quentin Fortier
Professeur d'informatique

Exercice à faire en C sur LeetCode pendant les vacances de Noël : https://leetcode.com/problems/find-champion-ii (facile)

Et pour ceux qui veulent plus difficile : https://leetcode.com/problems/shortest-cycle-in-a-graph

Indice

Pour le premier exercice, il s'agit de trouver s'il existe un unique sommet de degré entrant nul.

Pour le deuxième exercice, on peut utiliser un parcours en largeur : si on est en train de visiter un sommet u et qu'on trouve un voisin v de u qui est déjà visité, alors on a trouvé un cycle de longueur d[u] + d[v] + 1.

Solution
int findChampion(int n, int** edges, int edgesSize, int* edgesColSize) {
    int** g = (int**)malloc(sizeof(int*) * n);
    for (int i = 0; i < n; i++) {
        g[i] = (int*)malloc(sizeof(int) * n);
        for (int j = 0; j < n; j++)
            g[i][j] = 0;
    }
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0], v = edges[i][1];
        g[u][v] = 1;
    }
    int c = -1;
    for(int j = 0; j < n; j++) {
        int deg = 0;
        for (int i = 0; i < n; i++)
            deg += g[i][j];
        if(deg == 0) {
            if(c != -1) {
                return -1;
            }
            c = j;
        }
    }
    return c;
}

Colle 3 : Graphes et classes de complexité

Quentin Fortier
Quentin Fortier
Professeur d'informatique

Voici la liste des compétences et connaissances à avoir en colle ainsi que le DS 3.

Révisions sur les graphes : Tout le cours.

Arbres couvrants : Tout le cours.

Composantes fortement connexes et Kosaraju : Tout le cours.

Couplages et graphes bipartis : Tout le cours.

Plus courts chemins et A* : Tout le cours.

Décidabilité : Tout le cours.

Classes de complexité : Tout le cours.

Merci de poser obligatoirement au moins une question de décidabilité ou classe de complexité : montrer qu'un problème est indécidable (réduction depuis ARRET) ou NP-complet (NP + réduction polynomiale depuis SAT).

Algorithmes d'approximation et Branch and Bound : Tout le cours.

Algorithmes probabilistes : Tout le cours.

Colle 2 : Grammaires et graphes

Quentin Fortier
Quentin Fortier
Professeur d'informatique

Voici la liste des compétences et connaissances à avoir pour votre deuxième colle ainsi que le DS 2.

Grammaires :

  • Grammaire non-contextuelle (algébrique, hors-contexte).
  • Dérivation.
  • Langage engendré. Savoir démontrer par récurrence (sur la longueur du mot ou de la dérivation) que le langage engendré par G est bien ce qu'on souhaite.
  • Les langages réguliers sont algébriques.
  • Arbre de dérivation.
  • Grammaire ambigüe. Dérivation gauche. Savoir montrer qu'une grammaire est ambigüe.
  • Analyse syntaxique : exemple.

Révisions sur les graphes :

  • Définitions : degré, voisins...
  • Chemin, cycle, connexité.
  • Connexe à $n$ sommets $\Rightarrow$ au moins $n - 1$ arêtes.
  • Acyclique à $n$ sommets $\Rightarrow$ au plus $n - 1$ arêtes.
  • Composantes connexes, composantes fortement connexes.
  • Un graphe est un arbre ssi il est connexe acyclique ssi connexe et $n - 1$ arêtes ssi acyclique et $n - 1$ arêtes.
  • Représentations par matrice et liste d'adjacence.
  • Parcours en largeur et profondeur. Application à la connexité et à la recherche de cycle.

Arbres couvrants :

  • Définition.
  • Algorithme de Kruskal. Correction.
  • Union-Find avec compression de chemin et union par rang.

LeetCode 6

Quentin Fortier
Quentin Fortier
Professeur d'informatique

Exercice à faire en C sur LeetCode, au plus tard pour samedi prochain : https://leetcode.com/problems/maximum-subarray
Il est possible de résoudre cet exercice en O(n).

Indice

Parcourir nums[i] en conservant deux variables : la somme maximum finissant en nums[i] et la somme maximum trouvée jusqu'à présent.

Voir algorithme de Kadane.

Solution
int maxSubArray(int* nums, int numsSize) {
    int maxi = nums[0], max_cur = nums[0];
    for(int i = 1; i < numsSize; i++) {
        // invariant : max_cur est la somme consécutive max qui se termine en i
        max_cur = max_cur + nums[i];
        if(max_cur < nums[i])
            max_cur = nums[i];
        if(max_cur > maxi)
            maxi = max_cur;
    }
    return maxi;
}

LeetCode 5

Quentin Fortier
Quentin Fortier
Professeur d'informatique

Exercice à faire en C sur LeetCode, au plus tard pour samedi prochain : https://leetcode.com/problems/minimum-path-sum
Il s'agit d'un cas particulier de recherche de plus court chemin dans un graphe acyclique. Cela peut être résolu par programmation dynamique.

Indice

Calculer d[i][j] = la longueur minimum d'un chemin de (0, 0) à (i, j) en utilisant uniquement des déplacements vers le bas et vers la droite.

  1. Trouver une équation de récurrence pour b[i][j].
  2. Remplir le tableau b en utilisant cette équation de récurrence.
  3. Renvoyer la solution.
Solution
#include <math.h>

// On utilise la récurrence suivante :
// d[i][j] = grid[i][j] + min(d[i - 1][j], d[i][j - 1])

int minPathSum(int** grid, int gridSize, int* gridColSize) {
    int n = gridSize, p = gridColSize[0]; // nombres de lignes et colonnes
    int** d = malloc(n*sizeof(int*)); // d[i][j] = poids min d'un chemin de (0,0) à (i,j)
    for(int i = 0; i < n; i++) {
        d[i] = malloc(p*sizeof(int));
        for(int j = 0; j < p; j++) {
            int a = -1;
            if(i == 0 && j == 0)
                a = 0;
            if(i > 0)
                a = d[i - 1][j];
            if(j > 0 && (a == -1 || d[i][j - 1] < a))
                a = d[i][j - 1];
            d[i][j] = a + grid[i][j];
        }
    }
    return d[n - 1][p - 1];
}

LeetCode 4

Quentin Fortier
Quentin Fortier
Professeur d'informatique

Exercice à faire en C sur LeetCode, au plus tard pour samedi prochain : https://leetcode.com/problems/longest-palindromic-substring/description
Un palindrome est une chaîne qui se lit de la même façon dans les deux sens. Par exemple, "abba" est un palindrome. On cherche à trouver la plus grande sous-chaîne palindrome d'une chaîne donnée.

Indice

Un algorithme naïf qui regarde, pour tout i, j, si la sous-chaîne de s de i à j est un palindrome (= qui se lit de la même façon dans les deux sens), a une complexité O(n^3).

Pour que le programme soit accepté, on peut trouver une solution en O(n^2) par programmation dynamique. Pour cela :

  1. Définir un tableau b tel que b[i][j] vaut vrai si la sous-chaîne de s de i à j est un palindrome.
  2. Trouver une équation de récurrence pour b[i][j].
  3. Remplir le tableau b en utilisant cette équation de récurrence.
  4. Trouver la plus grande sous-chaîne palindrome en parcourant le tableau b.

On pourra utiliser la fonction suivante :

// Renvoie la sous-chaîne de s de l'indice i à j inclus
char* substring(char* s, int i, int j) {
    char* t = malloc(j - i + 2);
    for(int k = i; k <= j; k++)
        t[k - i] = s[k];
    t[j - i + 1] = '\0';
    return t;
}
Solution
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* subword(char* s, int i, int j) {
    char* t = malloc(j - i + 2);
    for(int k = i; k <= j; k++)
        t[k - i] = s[k];
    t[j - i + 1] = '\0';
    return t;
}

char* longestPalindrome(char* s) {
    int n = strlen(s);
    bool** b = malloc(n*sizeof(bool*));
    for(int i = 0; i < n; i++) {
        b[i] = malloc(n*sizeof(bool));
        for(int j = 0; j < n; j++) {
            b[i][j] = true;
        }
    }

    int imax = 0, kmax = 0;
    for(int k = 1; k < n; k++)
        for(int i = 0; i < n - k; i++) {
            b[i][i + k] = s[i] == s[i + k] && b[i + 1][i + k - 1];
            if(b[i][i + k]) {
                kmax = k;
                imax = i;
            }
        }
    return subword(s, imax, imax + kmax);
}