2 つのポインタ、表なし
なぜ大切か 「足すと X になる 2 つのものを見つける」には有名な答えがあります。すべてを集合に入れ、相手を調べるのです。速く、そしてすべてのデータの写しが要ります。データが並べられているなら、メモリはほとんど要りません。
贈り物のサービスが、違う 2 つの商品のセットを決まったセット価格で売ります。商品の価格の一覧は並べられていて、重複がなく、空きメモリのとても少ない組み込みの端末にあります。あるセット価格について、価格を足すとちょうどその価格になる商品の組の数が必要です。
prices = [1, 2, 3, 4, 5, 6] # sorted, no repeats
count_pairs(Tape(prices), 7) # 3: (1, 6), (2, 5), (3, 4)count_pairs(tape, target) を書いてください。tape は昇順に並べた、重複のない整数の価格の Tape です。足すとちょうど target になる違う 2 つの項目の組がいくつあるかを返します(それぞれの組は一度だけ数える)。予算:20,000 の項目で読むのは最大 60,000 の値、関数が動く間の作業用のメモリは最大 16,000 バイト(tracemalloc で測る。20,000 の価格の集合やリストは 150,000 バイトを超えます)。len(tape) は無料です。
この演習はまもなく開きます
その前のレッスンを終えると、このレッスンが解放されます。コース全体が無料でアカウントも不要、このレッスンは今すぐ読めます。
このブラウザは learn.floati.life の Cookie をブロックしているため、ここで修了したレッスンを順番どおりに開けません。このサイトの Cookie を許可して再読み込みしてください。