5 articles tagués avec « devoir »

Pour passer tous les tests, il faut implémenter l'algorithme de Dijkstra ce qui demande une file de priorité (tas min) et est un peu long à implémenter... On pourrait implémenter Floyd-Warshall ou Bellman-Ford à la place.

Solution

#include <stdbool.h>

int** createGraph(int n, int** edges, int edgesSize, int* edgesColSize) { // matrice d'adjacence
    int **g = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        g[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++)
            g[i][j] = -1;
    }
    for (int i = 0; i < edgesSize; i++) {
        int a = edges[i][0];
        int b = edges[i][1];
        int w = edges[i][2];
        g[a][b] = w;
        g[b][a] = w;
    }
    return g;
}

int** floydWarshall(int n, int** g) {
    int** dist = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        dist[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            if (i == j)
                dist[i][j] = 0;
            else if (g[i][j] != -1)
                dist[i][j] = g[i][j];
            else
                dist[i][j] = 1e9;
        }
    }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
    return dist;
}

bool* findAnswer(int n, int** edges, int edgesSize, int* edgesColSize, int* returnSize) {
    int** g = createGraph(n, edges, edgesSize, edgesColSize);
    int** dist = floydWarshall(n, g);
    bool* answer = (bool*)malloc(edgesSize * sizeof(bool));
    for (int i = 0; i < edgesSize; i++) {
        int a = edges[i][0];
        int b = edges[i][1];
        int w = edges[i][2];
        if (dist[0][a] + w + dist[b][n - 1] == dist[0][n - 1] ||
            dist[0][b] + w + dist[a][n - 1] == dist[0][n - 1])
            answer[i] = true;
        else
            answer[i] = false;
    }
    *returnSize = edgesSize;
    for (int i = 0; i < n; i++) {
        free(g[i]);
        free(dist[i]);
    }
    free(g);
    free(dist);
    return answer;
}

LeetCode 3 : Possible Bipartition

24 novembre 2025

Quentin Fortier

Professeur d'informatique

Exercice à faire en C sur LeetCode, avant lundi prochain : https://leetcode.com/problems/possible-bipartition

Solution

bool dfs(int u, int c, int* colors, int** g, int n) {
    colors[u] = c;
    for (int v = 1; v <= n; v++) {
        if (g[u][v]) { // il y a une arête entre u et v
            if (colors[v] == 0) {
                if (!dfs(v, -c, colors, g, n))
                    return false;
            } else if (colors[v] == c) {
                return false;
            }
        }
    }
    return true;
}

bool possibleBipartition(int n, int** dislikes, int dislikesSize, int* dislikesColSize) {
    int* colors = (int*)calloc(n + 1, sizeof(int)); // 0: non coloré, 1: rouge, -1: bleu
    int** g = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++)
        g[i] = (int*)calloc(n + 1, sizeof(int));
    for (int i = 0; i < dislikesSize; i++) {
        int u = dislikes[i][0];
        int v = dislikes[i][1];
        g[v][u] = g[u][v] = 1;
    }

    for (int i = 1; i <= n; i++) {
        if (colors[i] == 0 && !dfs(i, 1, colors, g, n))
            return false;
    }
    return true;
}

LeetCode 2 : Min Cost to Connect All Points

3 novembre 2025

Quentin Fortier

Professeur d'informatique

Exercice à faire en C sur LeetCode, avant lundi prochain : https://leetcode.com/problems/min-cost-to-connect-all-points

Indice

Utiliser l'algorithme de Kruskal sur le graphe dont les sommets sont les points et les arêtes sont les distances entre les points. Vous pouvez implémenter un tri fusion :

typedef struct {
    int n; // nombre de sommets
    int *degres; // degres[i] = nombre de voisins du sommet i
    arete **aretes; // aretes[i] = tableau des aretes incidentes au sommet i
} graphe;

arete a(int u, int v, int poids) {
    arete e;
    e.u = u;
    e.v = v;
    e.poids = poids;
    return e;
}

void fusion(arete* t, int n, arete* t1, int n1, arete* t2, int n2) {
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < n1 && j < n2) {
        if (t1[i].poids < t2[j].poids) {
            t[k] = t1[i];
            i++;
        } else {
            t[k] = t2[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        t[k] = t1[i];
        i++;
        k++;
    }
    while (j < n2) {
        t[k] = t2[j];
        j++;
        k++;
    }
}

// tri t de taille n entre les indices debut (inclus) et fin (exclus)
void tri_fusion(arete* t, int n, int debut, int fin) {
    if (fin - debut <= 1) {
        return;
    }
    int milieu = (debut + fin) / 2;
    tri_fusion(t, n, debut, milieu);
    tri_fusion(t, n, milieu, fin);
    arete* temp = malloc((fin - debut) * sizeof(arete));
    fusion(temp, fin - debut, &t[debut], milieu - debut, &t[milieu], fin - milieu);
    for (int i = debut; i < fin; i++) {
        t[i] = temp[i - debut];
    }
    free(temp);
}

Solution

typedef struct {
    int u;
    int v;
    int poids;
} arete;

typedef struct {
    int n; // nombre de sommets
    int *degres; // degres[i] = nombre de voisins du sommet i
    arete **aretes; // aretes[i] = tableau des aretes incidentes au sommet i
} graphe;

arete a(int u, int v, int poids) {
    arete e;
    e.u = u;
    e.v = v;
    e.poids = poids;
    return e;
}

typedef struct {
  int n; // nombre d'élements
  int* t; // t[i] = père de i
} uf;

uf* create(int n) {
    uf* u = malloc(sizeof(uf));
    u->n = n;
    u->t = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        u->t[i] = -1;
    }
    return u;
}

int find(uf* u, int x) {
    if (u->t[x] < 0) {
        return x;
    } else {
        int r = find(u, u->t[x]);
        u->t[x] = r;
        return r;
    }
}

void merge(uf* u, int x, int y) {
    int rx = find(u, x);
    int ry = find(u, y);
    if (rx < ry) u->t[ry] = rx;
    else if (rx > ry) u->t[rx] = ry;
    else {
        u->t[ry] = rx;
        u->t[rx]--;
    }
}

void fusion(arete* t, int n, arete* t1, int n1, arete* t2, int n2) {
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < n1 && j < n2) {
        if (t1[i].poids < t2[j].poids) {
            t[k] = t1[i];
            i++;
        } else {
            t[k] = t2[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        t[k] = t1[i];
        i++;
        k++;
    }
    while (j < n2) {
        t[k] = t2[j];
        j++;
        k++;
    }
}

void tri_fusion(arete* t, int n, int debut, int fin) {
    if (fin - debut <= 1) {
        return;
    }
    int milieu = (debut + fin) / 2;
    tri_fusion(t, n, debut, milieu);
    tri_fusion(t, n, milieu, fin);
    arete* temp = malloc((fin - debut) * sizeof(arete));
    fusion(temp, fin - debut, &t[debut], milieu - debut, &t[milieu], fin - milieu);
    for (int i = debut; i < fin; i++) {
        t[i] = temp[i - debut];
    }
    free(temp);
}

int minCostConnectPoints(int** points, int pointsSize, int* pointsColSize) {
    arete* t = malloc(pointsSize * (pointsSize - 1) / 2 * sizeof(arete));
    int k = 0;
    for (int i = 0; i < pointsSize; i++) {
        for (int j = i + 1; j < pointsSize; j++) {
            t[k] = a(i, j, abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]));
            k++;
        }
    }
    tri_fusion(t, pointsSize * (pointsSize - 1) / 2, 0, pointsSize * (pointsSize - 1) / 2);
    uf* u = create(pointsSize);
    int res = 0;
    for (int i = 0; i < pointsSize * (pointsSize - 1) / 2; i++) {
        if (find(u, t[i].u) != find(u, t[i].v)) {
            res += t[i].poids;
            merge(u, t[i].u, t[i].v);
        }
    }
    free(u->t);
    free(u);
    free(t);
    return res;
}

LeetCode 1 : Number of Islands

18 octobre 2025

Quentin Fortier

Professeur d'informatique

Vous devez vous inscrire sur https://leetcode.com (en cliquant sur Create Account).
Exercice à faire en C sur LeetCode : https://leetcode.com/problems/number-of-islands
Une vidéo explicative pour utiliser LeetCode : https://youtu.be/q5dEFWMO8-o

Indice

Le problème revient à calculer les composantes connexes du graphe dont les sommets sont les cases de la grille et où chaque case a 4 arêtes possibles avec les cases voisines.
Pour calculer le nombre de composantes connexes, on peut utiliser un parcours en profondeur (ou en largeur). On peut directement utiliser grid comme tableau des vus (en mettant une case à '0' après l'avoir visitée).

// Parcours en profondeur depuis la case (i, j)
void dfs(char** grid, int n, int p, int i, int j) {
    ...
}

int numIslands(char** grid, int gridSize, int* gridColSize) {
    int n = gridSize, p = gridColSize[0]; // n lignes, p colonnes
    int k = 0; // nombre de composantes connexes
    for(int i = 0; i < n; i++)
        for(int j = 0; j < p; j++)
            ...
    return k;
}

Solution

// Solution en O(l) avec un parcours en profondeur, où l = np est le nombre de cases de la grille
// Plutôt qu'utiliser une matrice de booléens vus, on peut mettre les cases visitées à 0 pour éviter de les revisiter

void dfs(char** grid, int n, int p, int i, int j) {
    if(grid[i][j] == '0') return;
    grid[i][j] = '0';
    if(i > 0) // chaque sommet a 4 voisins
        dfs(grid, n, p, i - 1, j);
    if(i < n - 1)
        dfs(grid, n, p, i + 1, j);
    if(j > 0)
        dfs(grid, n, p, i, j - 1);
    if(j < p - 1)
        dfs(grid, n, p, i, j + 1);
}

int numIslands(char** grid, int gridSize, int* gridColSize) {
    int n = gridSize, p = gridColSize[0];
    int k = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < p; j++)
            if(grid[i][j] == '1') {
                dfs(grid, n, p, i, j);
                k++;
            }
    return k;
}