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).
Parcourir nums[i] en conservant deux variables : la somme maximum finissant en nums[i] et la somme maximum trouvée jusqu'à présent.
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.
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.
#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];
}
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.
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 :
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;
}
#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);
}
Exercice à faire en C sur LeetCode, au plus tard pour samedi prochain : https://leetcode.com/problems/number-of-islands
Cela 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;
}
Si besoin, vous pouvez revoir le cours de 1ère année.
// 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;
}
Exercice à faire en C sur LeetCode, au plus tard pour samedi prochain : https://leetcode.com/problems/merge-two-sorted-lists
On pourra écrire une fonction récursive.
Si vous avez terminé l'exercice, vous pouvez faire ce prolongement (plus difficile) : https://leetcode.com/problems/merge-k-sorted-lists
Réutiliser la fonction précédente pour fusionner deux listes.
L'idéal est de résoudre ce problème en O(n log (k)) où n est la somme des tailles des listes et k le nombre de listes.
Solution en O(nlog(k)) avec une approche diviser pour régner (où n = somme des tailles des listes et k = nombre de listes) :
l1 = fusionner récursivement les k/2 premières listesl2 = fusionner récursivement les k/2 dernières listesl1 et l2Chaque fusion s'effectue en O(n) et il y a log(k) fusions, d'où la complexité en O(nlog(k))
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
if (list1 == NULL) return list2;
if (list2 == NULL) return list1;
if (list1->val <= list2->val) {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
if (list1->val > list2->val) {
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
return NULL;
}
struct ListNode* merge(struct ListNode** lists, int i, int j) {
if(i + 1 == j) return lists[i];
if(i == j) return NULL;
int m = (i + j)/2;
return mergeTwoLists(merge(lists, i, m), merge(lists, m, j));
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
return merge(lists, 0, listsSize);
}
Voici le premier exercice à faire en C sur LeetCode, au plus tard pour dimanche prochain (15 septembre) : https://leetcode.com/problems/longest-substring-without-repeating-characters
Une vidéo explicative pour utiliser LeetCode : https://youtu.be/q5dEFWMO8-o
Vous pouvez me demander de l'aide par mail.
// 1ere solution : O(n^3) en regardant, pour chaque sous-chaîne, si elle contient un doublon
int lengthOfLongestSubstring(char* s) {
int max = 0;
for(int i = 0; i < strlen(s); i++) {
int j = i + 1;
int b = 0;
while(j < strlen(s)) {
for(int k = i; k < j; k++) {
if(s[k] == s[j])
b = 1;
}
if(b) break;
j++;
}
if(j - i > max)
max = j - i;
}
return max;
}
// 2eme solution : O(n^2) en conservant un tableau count pour savoir si un caractère est déjà présent dans la sous-chaîne
// on utilise un tableau de 256 éléments pour les caractères ASCII
int lengthOfLongestSubstring(char* s) {
int max = 0;
int n = strlen(s);
for(int i = 0; i < n; i++) {
int j = i;
int count[256] = {0};
while(j < n && count[s[j]] == 0) {
count[s[j]] = 1;
j++;
}
if(j - i > max)
max = j - i;
}
return max;
}
Vous devez vous inscrire sur https://leetcode.com (en cliquant sur Create Account). Envoyez-moi ensuite votre nom d'utilisateur par mail pour que je puisse vérifier votre progression.
Une vidéo explicative pour utiliser LeetCode : https://youtu.be/q5dEFWMO8-o