1. Compression basique d'images

Nous devons implémenter un algorithme de compression d'images en niveaux de gris. Chaque pixel est représenté par un entier entre 0 et 255. L'algorithme regroupe les pixels identiques adjacents dans chaque ligne d'image.

L'entrée est une matrice 2D d'entiers représentant l'image, et la sortie doit être une structure de données contenant des paires d'entiers (valeur du pixel, nombre d'occurrences consécutives).

Voici l'implémentation :

#include <vector>
#include <utility>
using namespace std;

vector<vector<pair<int, int>>> compresserImage(const vector<vector<int>>& image) {
    vector<vector<pair<int, int>>> resultat;
    
    if (image.empty()) return resultat;
    
    for (const auto& ligne : image) {
        vector<pair<int, int>> ligneCompressee;
        
        if (ligne.empty()) {
            resultat.push_back(ligneCompressee);
            continue;
        }
        
        int valeurCourante = ligne[0];
        int compteur = 1;
        
        for (size_t i = 1; i < ligne.size(); ++i) {
            if (ligne[i] == valeurCourante) {
                compteur++;
            } else {
                ligneCompressee.push_back(make_pair(valeurCourante, compteur));
                valeurCourante = ligne[i];
                compteur = 1;
            }
        }
        
        ligneCompressee.push_back(make_pair(valeurCourante, compteur));
        resultat.push_back(ligneCompressee);
    }
    
    return resultat;
}

2. Calcul de ventes moyennes

Nous devons traiter des requêtes pour calculer la moyenne des ventes entre deux régions, ainsi que des mises à jour des ventes pour une région spécifique.

L'entrée comprend un nombre N de régions et un nombre M d'opérations. Les opérations peuvent être de type requête (Q A B) ou mise à jour (U A B).

Voici l'implémentation utilisant un tableau et un tableau de sommes préfixées :

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int nbRegions, nbOperations;
    cin >> nbRegions >> nbOperations;
    
    vector<long long> ventes(nbRegions + 1, 0);
    vector<long long> sommePrefixee(nbRegions + 1, 0);
    
    for (int i = 1; i <= nbRegions; ++i) {
        cin >> ventes[i];
        sommePrefixee[i] = sommePrefixee[i-1] + ventes[i];
    }
    
    while (nbOperations--) {
        char operation;
        int A, B;
        cin >> operation >> A >> B;
        
        if (operation == 'Q') {
            long long total = sommePrefixee[B] - sommePrefixee[A-1];
            int moyenne = static_cast<int>(total / (B - A + 1));
            cout << moyenne << endl;
        } else if (operation == 'U') {
            ventes[A] += B;
            for (int i = A; i <= nbRegions; ++i) {
                sommePrefixee[i] = sommePrefixee[i-1] + ventes[i];
            }
        }
    }
    
    return 0;
}

3. Inversion d'une liste chaînée

Nous devons inverser une liste chaînée simple et renvoyer la nouvelle tête de liste.

Voici l'implémentation de la structure de nœud et de la fonction d'inversion :

struct Noeud {
    int valeur;
    Noeud* suivant;
    Noeud(int val) : valeur(val), suivant(nullptr) {}
};

Noeud* inverserListe(Noeud* tete) {
    Noeud* precedent = nullptr;
    Noeud* courant = tete;
    
    while (courant) {
        Noeud* suivant = courant->suivant;
        courant->suivant = precedent;
        precedent = courant;
        courant = suivant;
    }
    
    return precedent;
}