Bereken vooraf een keer
Waarom dit saak maak "Totaal van X tussen twee punte" is een van die algemeenste vrae in rapporteringskode. Om elk een deur die reeks bymekaar te tel is stadig; om 'n totaal vir elke punt te hou kan te groot wees. Daar is 'n roete tussen die twee.
A winkel hou 60,000 dae se verkope op 'n metered store, wat aan jou gegee word as 'n Tape. Finansie stuur 'n pakkie van 50 vrae gelyktydig: "totale verkope vanaf dag a tot dag b". Jy hardloop op 'n klein worker met baie min vrye geheue.
Lopende totaal (prefix sum): die som van alles voor 'n posisie. Die totaal van 'n venster is die lopende totaal by die einde minus die lopende totaal by die begin.
sales = [5, 1, 4, 2, 8]
# running totals before each position: 0, 5, 6, 10, 12, 20
# window (1, 4) = 12 - 5 = 7Skryf range_totals(tape, queries). tape is 'n Tape van daaglikse verkope (heeltallige getalle). queries is 'n lys van (start, end)-paaie met 0 <= start <= end <= len(tape). Gee 'n lys met die totaal van tape[start:end] vir elke navraag, in die volgorde wat gegee word. Budgets: lees die band hoogstens een keer (60,100 leesies vir 60,000 dae en 50 navrae), en gebruik hoogstens 100,000 bytes van werksgeheue terwyl jou funksie loop (gemeet met tracemalloc; 'n lopende totaal vir elke dag, of selfs 'n eenvoudige lys van die 60,000 waardes, is ver bo 100,000 bytes). Die vrae kom almal gelyk saam aan, voordat jy die data lees.
Sien jy 'n probleem in hierdie les? Rapporteer dit · Vra oor hierdie les
Hierdie oefening open binnekort
Voltooi die lesie voor dit en hierdie een sal ontvanklik wees. Die hele kursus is gratis, geen rekening nodig nie, en jy kan hierdie les nou lees.
Hierdie blutser blokkeer koekies vir learn.floati.life, so lesse wat jy hier voltooi het kan nie in volgorde oopgaan nie. Laat koekies vir hierdie webwerf toe en laai nuut.