Aller au contenu principal

5 articles tagués avec « leetcode »

Voir tous les tags

LeetCode 5

Quentin Fortier
Quentin Fortier
Professeur d'informatique

Deux exercices LeetCode pour ces vacances.

Indice 1er exercice

Parcourir chaque indice du tableau en conservant la somme maximale se terminant à cet indice.

Indice 2ème exercice

Utiliser un algorithme par programmation dynamique en calculant b[i][j] qui vaut vrai si la sous-chaîne d'indice i à j est un palindrome.

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;
}
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);
}

LeetCode 4 : Find Edges in Shortest Paths

Quentin Fortier
Quentin Fortier
Professeur d'informatique

Exercice à faire en C sur LeetCode cette semaine : https://leetcode.com/problems/find-edges-in-shortest-paths/description/

Il y a deux indices en bas de la page (Hint).

Details

Indice 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

Quentin Fortier
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

Quentin Fortier
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

Quentin Fortier
Quentin Fortier
Professeur d'informatique
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;
}