問題タブ [prefix-sum]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
kotlin - Kotlin で O(n) 時間で純粋に関数型プログラミング スタイルですべてのプレフィックスの合計を計算する
KotlinでO(n)時間で純粋関数型プログラミングスタイルの数値配列のすべてのプレフィックス合計を計算することは可能ですか?
純粋な関数型プログラミングとは、 _Collections,ktmapで、reduce、fold、sumなどのコレクションのみに関数型プログラミング拡張関数を使用できるようにすることを意味しますが、通常のループ、可変変数別名などの状態と可変データの変更を含む従来の命令型プログラミング方法を使用できます。s、および変更可能な配列は許可されていません。(これはウィキペディアの定義に準拠していると思います)var
より具体的に言うと、O(n) 時間で実行される命令型プログラミングで書かれた達成したいことの一例と、O(n^2) 時間で実行される関数型プログラミングで書かれた別の例があります。
matrix - Leetcode 1314 でのヒープ オーバーフロー
質問: https://leetcode.com/problems/matrix-block-sum/
sum[i][j]要素とその行と列を含む左側のすべての要素の合計である2Dプレフィックスサムを使用して解決しようとしています。
コード :
java - 接頭辞と接尾辞の合計の計算の背後にある直感
LeetCode の質問を解決しています: すべてのボールを各ボックスに移動するための操作の最小数。
n箱があります。長さ のバイナリ文字列ボックスが与えられますn。ここでboxes[i]、th ボックスが空の場合は '0'、iボールが 1 つ含まれている場合は '1' です。1 回の操作で、ボックスから隣接するボックスに 1 つのボールを移動できます。size の配列回答を返しますn。ここで、はすべてのボールをth ボックスanswer[i]に移動するために必要な操作の最小数です。i入力boxes = "001011"の場合、出力は次のとおり[11,8,5,4,3,4]です。
それを行うことO(n^2)は簡単です。その方法でしか解決できませんでした。私はこの O(n)解決策を理解しようとしていますが、苦労しています:
誰かが背後にあるロジックを詳しく説明してください:
ボールに遭遇するたびにインクリメントすることは理解していますが、左側のすべてのボールを に移動するためにこれまでに必要な操作の数をカウントするcountのにどのように役立ちますか(の場合はその逆)?left[i] = left[i - 1] + count;iright
ありがとうございました！