1686. Jeu de pierres VI

Dans ce jeu, Alice et Bob jouent à tour de rôle, avec Alice commençant. Il y a n pierres, et à chaque tour, un joueur retire une pierre et obtient une valeur. Les deux joueurs ont des évaluations différentes des pierres, représentées par les tableaux aliceValues et bobValues. Le joueur avec le score le plus élevé à la fin gagne ; en cas d'égalité, c'est un match nul. Les deux joueurs jouent de manière optimale.

Exemple :

• Entrée : aliceValues = [1,3], bobValues = [2,1] → Sortie : 1
• Entrée : aliceValues = [1,2], bobValues = [3,1] → Sortie : 0
• Entrée : aliceValues = [2,4,3], bobValues = [1,6,7] → Sortie : -1

Contraintes : n <= 1e5, valeurs <= 100.

Approche gloutonne :

class Solution {
public:
    int stoneGameVI(vector<int>& valA, vector<int>& valB) {
        int cnt = valA.size();
        vector<pair int="">> data(cnt);
        for (int i = 0; i < cnt; ++i) {
            data[i] = {valA[i] + valB[i], i};
        }
        sort(data.begin(), data.end(), greater<pair int="">>());
        int totalA = 0, totalB = 0;
        for (int i = 0; i < cnt; ++i) {
            int idx = data[i].second;
            if (i % 2 == 0) totalA += valA[idx];
            else totalB += valB[idx];
        }
        if (totalA > totalB) return 1;
        if (totalA < totalB) return -1;
        return 0;
    }
};</pair></pair></int></int>

1690. Jeu de pierres VII

Alice et Bob jouent avec n pierres alignées. À chaque tour, un joueur retire la pierre la plus à gauche ou la plus à droite, et obtient un score égal à la somme des valeurs des pierres restantes. Le joueur avec le score le plus élevé gagne. Bob cherche à minimiser la différence de score, tandis qu'Alice cherche à la maximiser. Retourner la différence de score optimale.

Exemple :

• Entrée : stones = [5,3,1,4,2] → Sortie : 6
• Entrée : stones = [7,90,5,1,100,10,10,2] → Sortie : 122

Contraintes : n <= 1000, valeurs <= 1000.

Approceh par programmation dynamique de jeu :

class Solution {
    int prefixSum[1010];
    int dp[1010][1010];

public:
    int stoneGameVII(vector<int>& stones) {
        int n = stones.size();
        for (int i = 1; i <= n; i++)
            prefixSum[i] = prefixSum[i - 1] + stones[i - 1];
        for (int i = 1; i <= n; i++)
            dp[i][i] = stones[i - 1];
        for (int i = n; i >= 1; i--) {
            for (int j = i + 1; j <= n; j++) {
                int leftOption = prefixSum[j] - prefixSum[i] - dp[i + 1][j];
                int rightOption = prefixSum[j - 1] - prefixSum[i - 1] - dp[i][j - 1];
                dp[i][j] = min(leftOption, rightOption);
            }
        }
        return prefixSum[n] - dp[1][n];
    }
};</int>

292. Jeu de Nim

Dans ce jeu, deux joueurs retirent alternativement 1 à 3 pierres d'un tas. Le joueur qui retire la dernière pierre gagne. Déterminer si le premier joueur peut gagner avec n pierres, en supposant un jeu optimal.

Exemple :

• Entrée : n = 4 → Sortie : false
• Entrée : n = 1 → Sortie : true
• Entrée : n = 2 → Sortie : true

Solution mathématique :

class Solution {
public:
    bool canWinNim(int stones) {
        return stones % 4 != 0;
    }
};

1696. Jeu de saut VI

Étant donné un tableau nums et un entier k, commencer à l'indice 0. À chaque étape, sauter au plus k pas en avant, sans dépasser les limites. L'objectif est d'atteindre le dernier indice avec la somme maximale des valeurs traversées.

Exemple :

• Entrée : nums = [1,-1,-2,4,-7,3], k = 2 → Sortie : 7
• Entrée : nums = [10,-5,-2,4,0,3], k = 3 → Sortie : 17
• Entrée : nums = [1,-5,-20,4,-1,3,-6,-3], k = 2 → Sortie : 0

Contraintes : n, k <= 1e5, -1e4 <= nums[i] <= 1e4.

Approche avec file d'attente monotone et DP :

class Solution {
public:
    int maxResult(vector<int>& arr, int maxJump) {
        deque<int> dq;
        dq.push_back(0);
        for (int i = 1; i < arr.size(); i++) {
            if (dq.front() < i - maxJump) dq.pop_front();
            arr[i] += arr[dq.front()];
            while (!dq.empty() && arr[i] >= arr[dq.back()]) dq.pop_back();
            dq.push_back(i);
        }
        return arr.back();
    }
};</int></int>

LCP 30. Tour magique

Un joueur commence avec 1 point de vie dans une tour de N pièces. Chaque pièce a un effet positif (soin) ou négatif (dégât). Le joueur peut déplacer une pièce négative à la fin de la séquence. Trouver le nombre minimal de déplacements nécessaires pour visiter toutes les pièces sans tomber à 0 point de vie, ou -1 si impossible.

Exemple :

• Entrée : nums = [100,100,100,-250,-60,-140,-50,-50,100,150] → Sortie : 1
• Entrée : nums = [-200,-300,400,0] → Sortie : -1

Contraintes : 1 <= n <= 1e5, -1e5 <= nums[i] <= 1e5.

Approche gloutonne avec file de priorité :

class Solution {
public:
    int magicTower(vector<int>& rooms) {
        long long totalSum = 0;
        for (int val : rooms) totalSum += val;
        if (totalSum < 0) return -1;
        int moves = 0;
        long long hp = 1;
        priority_queue<int vector="">, greater<int>> minHeap;
        for (int val : rooms) {
            minHeap.push(val);
            while (hp + val <= 0) {
                moves++;
                hp -= minHeap.top();
                minHeap.pop();
            }
            hp += val;
        }
        return moves;
    }
};</int></int></int>

2641. Cousins dans l'arbre binaire II

Dans un arbre binaire, remplacer chaque valeur de nœud par la somme des valeurs de tous ses cousins (nœuds au même niveau mais avec des parents différents).

Exemple :

• Entrée : root = [5,4,9,1,10,null,7] → Sortie : [0,0,0,7,7,null,11]

Contraintes : 1 <= n <= 1e5, 1 <= Node.val <= 1e4.

Approche par BFS avec deux passes :

class Solution {
public:
    TreeNode* replaceValueInTree(TreeNode* root) {
        root->val = 0;
        vector<treenode> currentLevel = {root};
        while (!currentLevel.empty()) {
            vector<treenode> nextLevel;
            int nextLevelSum = 0;
            for (TreeNode* node : currentLevel) {
                if (node->left) {
                    nextLevel.push_back(node->left);
                    nextLevelSum += node->left->val;
                }
                if (node->right) {
                    nextLevel.push_back(node->right);
                    nextLevelSum += node->right->val;
                }
            }
            for (TreeNode* node : currentLevel) {
                int childrenSum = (node->left ? node->left->val : 0) +
                                  (node->right ? node->right->val : 0);
                if (node->left) node->left->val = nextLevelSum - childrenSum;
                if (node->right) node->right->val = nextLevelSum - childrenSum;
            }
            currentLevel = move(nextLevel);
        }
        return root;
    }
};</treenode></treenode>

993. Cousins dans l'arbre binaire

Étant donné un arbre binaire et deux valeurs x et y, déterminer si les nœuds correspondants sont cousins (même niveau, parents différents).

Exemple :

• Entrée : root = [1,2,3,4], x = 4, y = 3 → Sortie : false
• Entrée : root = [1,2,3,null,4,null,5], x = 5, y = 4 → Sortie : true

Contraintes : 2 <= n <= 100, valeurs uniques de 1 à 100.

Approche par DFS :

class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        bool found = false;
        int depthX = -1, depthY = -1;
        TreeNode* parentX = nullptr;
        TreeNode* parentY = nullptr;
        function<void int="" treenode=""> dfs = [&](TreeNode* node, TreeNode* parent, int d) {
            if (!node) return;
            if (node->val == x) {
                depthX = d;
                parentX = parent;
            }
            if (node->val == y) {
                depthY = d;
                parentY = parent;
            }
            if (depthX != -1 && depthY != -1) {
                found = (depthX == depthY) && (parentX != parentY);
                return;
            }
            dfs(node->left, node, d + 1);
            dfs(node->right, node, d + 1);
        };
        dfs(root, nullptr, 1);
        return found;
    }
};</void>

236. Plus proche ancêtre commun d'un arbre binaire

Trouver le plus proche ancêtre commun de deux nœuds p et q dans un arbre binaire.

Exemple :

• Entrée : root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 → Sortie : 3
• Entrée : p = 5, q = 4 → Sortie : 5

Contraintes : 2 <= n <= 1e5, valeurs uniques.

Approche récursive :

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;
        TreeNode* leftResult = lowestCommonAncestor(root->left, p, q);
        TreeNode* rightResult = lowestCommonAncestor(root->right, p, q);
        if (leftResult && rightResult) return root;
        return leftResult ? leftResult : rightResult;
    }
};

94. Parcours infixe d'un arbre binaire

Retourner le parcousr infixe (left, root, right) d'un arbre binaire.

Exemple :

• Entrée : root = [1,null,2,3] → Sortie : [1,3,2]

Contraintes : 0 <= n <= 100, -100 <= Node.val <= 100.

Approche récursive :

class Solution {
    void traverseInorder(TreeNode* node, vector<int>& res) {
        if (!node) return;
        traverseInorder(node->left, res);
        res.push_back(node->val);
        traverseInorder(node->right, res);
    }
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traverseInorder(root, result);
        return result;
    }
};</int></int></int>

144. Parcours préfixe d'un arbre binaire

Retourner le parcours préfixe (root, left, right) d'un arbre binaire.

Exemple :

• Entrée : root = [1,null,2,3] → Sortie : [1,2,3]

Contraintes : 0 <= n <= 100, -100 <= Node.val <= 100.

Approche récursive :

class Solution {
    void traversePreorder(TreeNode* node, vector<int>& res) {
        if (!node) return;
        res.push_back(node->val);
        traversePreorder(node->left, res);
        traversePreorder(node->right, res);
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversePreorder(root, result);
        return result;
    }
};</int></int></int>

145. Parcours postfixe d'un arbre binaire

Retoruner le parcours postfixe (left, right, root) d'un arbre binaire.

Exemple :

• Entrée : root = [1,null,2,3] → Sortie : [3,2,1]

Contraintes : 0 <= n <= 100, -100 <= Node.val <= 100.

Approche récursive :

class Solution {
    void traversePostorder(TreeNode* node, vector<int>& res) {
        if (!node) return;
        traversePostorder(node->left, res);
        traversePostorder(node->right, res);
        res.push_back(node->val);
    }
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        traversePostorder(root, result);
        return result;
    }
};</int></int></int>

987. Parcours vertical d'un arbre binaire

Calculer le parcours vertical d'un arbre binaire, où les nœuds sont groupés par colonne, triés par rang puis par valeur.

Exemple :

• Entrée : root = [3,9,20,null,null,15,7] → Sortie : [[9],[3,15],[20],[7]]

Contraintes : 1 <= n <= 1000, 0 <= Node.val <= 1000.

Approche par DFS et hachage :

class Solution {
    map<int int="" vector="">>> columnMap;
    void dfs(TreeNode* node, int row, int col) {
        if (!node) return;
        columnMap[col].emplace_back(row, node->val);
        dfs(node->left, row + 1, col - 1);
        dfs(node->right, row + 1, col + 1);
    }
public:
    vector<vector>> verticalTraversal(TreeNode* root) {
        dfs(root, 0, 0);
        vector<vector>> ans;
        for (auto& [col, nodes] : columnMap) {
            sort(nodes.begin(), nodes.end());
            vector<int> vals;
            for (auto& [row, val] : nodes) vals.push_back(val);
            ans.push_back(vals);
        }
        return ans;
    }
};</int></vector></vector></int>

102. Parcours par niveau d'un arbre binaire

Retourner le parcours par niveau (de gauche à droite) d'un arbre binaire.

Exemple :

• Entrée : root = [3,9,20,null,null,15,7] → Sortie : [[3],[9,20],[15,7]]

Contraintes : 0 <= n <= 2000, -1000 <= Node.val <= 1000.

Approche par BFS avec file d'attente :

class Solution {
public:
    vector<vector>> levelOrder(TreeNode* root) {
        queue<treenode> q;
        vector<vector>> result;
        if (root) q.push(root);
        while (!q.empty()) {
            int levelSize = q.size();
            vector<int> currentLevel;
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front(); q.pop();
                currentLevel.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            result.push_back(currentLevel);
        }
        return result;
    }
};</int></vector></treenode></vector>

107. Parcours par niveau inversé d'un arbre binaire

Retourner le parcours par niveau du bas vers le haut d'un arbre binaire.

Exemple :

• Entrée : root = [3,9,20,null,null,15,7] → Sortie : [[15,7],[9,20],[3]]

Contraintes : 0 <= n <= 2000, -1000 <= Node.val <= 1000.

Approche par BFS suivie d'une inversion :

class Solution {
public:
    vector<vector>> levelOrderBottom(TreeNode* root) {
        queue<treenode> q;
        vector<vector>> result;
        if (root) q.push(root);
        while (!q.empty()) {
            int levelSize = q.size();
            vector<int> currentLevel;
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front(); q.pop();
                currentLevel.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            result.push_back(currentLevel);
        }
        reverse(result.begin(), result.end());
        return result;
    }
};</int></vector></treenode></vector>