Accueil › Coding & algorithmique › Beaucoup de questions, un seul prétraitement
Beaucoup de questions, un seul prétraitement
Exercice de la série « Tableaux et parcours »intermediaire
Le problème. Un tableau de ventes journalières, et des centaines de
questions de la forme « quel est le total du jour i au jour j,
bornes incluses ? ». Resommer à chaque question coûte trop cher.
Écrivez totaux(ventes, questions) où questions est un tableau de
paires [i, j]. Renvoyez un tableau avec un total par question, dans le
même ordre.
| Appel | Résultat attendu |
|---|---|
totaux([1, 2, 3, 4], [[0, 1], [1, 3], [2, 2]]) |
[3, 9, 3] |
totaux([5], [[0, 0]]) |
[5] |
totaux([], []) |
[] |
totaux([1, 2], [[0, 1], [0, 0], [1, 1]]) |
[3, 1, 2] |
Ce qu'on attend. Un prétraitement en O(n), puis O(1) par question.
Le piège. Les bornes sont incluses, et un tableau de sommes préfixes est décalé d'une case par rapport au tableau d'origine. Le décalage est là, et nulle part ailleurs.
Cas de test
[[1,2,3,4],[[0,1],[1,3],[2,2]]][[5],[[0,0]]][[],[]][[1,2],[[0,1],[0,0],[1,1]]][[2,-3,5,1],[[0,3],[1,2]]][[4,4,4],[[0,2]]]
Votre code s'exécute réellement dans le navigateur, et la correction compare son résultat à celui d'une solution de référence.