Предвычислите один раз
Почему это важно "Сумма X между двумя точками" - один из самых частых вопросов в коде отчётов. Отвечать на каждый, складывая диапазон, медленно; хранить сумму для каждой точки может оказаться слишком объёмно. Между этими двумя есть путь.
Магазин хранит 60 000 дней продаж в хранилище с учётом чтений, и они даются вам как Tape. Финансовый отдел присылает пакет из 50 вопросов сразу: "сумма продаж с дня a до дня b". Вы работаете на маленьком обработчике с очень небольшим запасом памяти.
Накопленная сумма (префиксная сумма): сумма всего, что стоит до позиции. Сумма окна - это накопленная сумма в его конце минус накопленная сумма в его начале.
sales = [5, 1, 4, 2, 8]
# running totals before each position: 0, 5, 6, 10, 12, 20
# window (1, 4) = 12 - 5 = 7Напишите range_totals(tape, queries). tape - это Tape ежедневных продаж (целые числа). queries - список пар (start, end) с 0 <= start <= end <= len(tape). Верните список с суммой tape[start:end] для каждого запроса в данном порядке. Бюджеты: прочитать ленту не больше одного раза (60 100 чтений для 60 000 дней и 50 запросов) и использовать не больше 100 000 байт рабочей памяти, пока работает функция (измеряется через tracemalloc; накопленная сумма для каждого дня или даже простой список из 60 000 значений - намного больше 100 000 байт). Все вопросы приходят вместе, до того как вы читаете данные.
Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке
Это упражнение откроется скоро
Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.
Этот браузер блокирует cookies для learn.floati.life, поэтому завершенные здесь уроки не могут открыться по порядку. Разрешите cookies для этого сайта и перезагрузите страницу.