Geen cache: geërfde afslagverkortinge
Waarom dit saak maak "Dit herhaal werk, so onthou die antwoorde" is een van die sterkste gewoontes in programmering, mens of KI. Soms hoef die werk glad nie herhaal te word nie.
A winkel se kategorieë vorm 'n boom: Tuin sit onder Huis, Gereedskap onder Tuin, en so aan. 'n Bemarkingsbestuurder kan 'n afslag op enige kategorie stel, en dit geld vir alles daaronder tensy 'n nader kategorie sy eie stel. Die checkout soek die effektiewe afslag vir duisende kategorieë gelyktydig op.
Die data
parents = {"home": None, "garden": "home", "tools": "garden", "seeds": "garden"}
own = {"garden": 10, "seeds": 25} # discounts set directly, in percent
queries = ["tools", "seeds", "home"]
# effective_discounts(parents, own, queries) -> [10, 25, 0]Die duidelike oplossing vir herhaalde stappe op die boom is 'n cache. In hierdie probleem is caches verbied. Soek 'n manier wat die werk nooit herhaal nie.
Skryf effective_discounts(parents, own, queries). parents koppel elke kategorie na sy ouer, of None vir 'n topvlak-kategorie (daar kan verskeie wees, en die dict is in geen spesifieke volgorde nie). own koppel sommige kategorieë na hul eie afslag. Vir elke kategorie in queries, gee die afslag van die naaste kategorie op sy pad na die top, beginnend by homself, wat een in own het; 0 as geen een het nie. Rule: geen cache of memo: geen functools cache decorators, geen naam wat "cache" of "memo" bevat, en geen werkende antwoorde uit as die navrae daarvoor vra en dit hou ('n memo onder 'n ander naam). Gaan deur die hele boom eerste, dan lees die navrae. Budget: maksimum 500,000 stappe (steps()) vir 3,000 kategorieë, bome tot 'n paar honderd vlakke diep, en 20,000 soektogte.
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.