LeetCode の K 要素パターンを理解する: 基本 (パート 1)

やっと分かりました！ LeetCode を学習する最善の方法は、次から次へと問題を徹底的に解いていくことではなく、場合によっては非効率的に解決するのに 1 時間もかかってしまいます。 LeetCode をマスターする鍵はパターンを学ぶことです。よくあることを勉強しましょう！

面接官は、文字列または配列内の K 個の要素の検索、維持、操作について質問するのが好きです。最初はそれぞれの問題がまったく異なるものだと思っていましたが、その後、関連性が見え始めました。このパターンを理解するのに本当に役立つ 2 つの問題について、私が何を意味するのかを説明しましょう。

問題 1: 合計が最大となる長さ K の部分列を見つけます

これは技術的には「簡単」レベルの質問 (1 社のみが質問) ですが、これらの k 要素の問題についてどのように考えるかについて多くのことを教えてくれます。

彼らが尋ねていること

数値の配列と値 k を取得します。配列から合計が最大になる k 個の数値を見つける必要があります。ただし (これが最初に私をつまずかせた部分です)、数字は元の順序に保たなければなりません!

例:

ああ！これはさらに厄介です:

わかりました

最初は、「k 個の最大の数字を取得すれば完了!」と思いました。しかし、いいえ、その注文要件によってすべてが変わります。最終的にクリックしたものは次のとおりです:

1. それぞれの数字がどこから来たのかを覚えておく必要がありますよね?それで 私は、「すべての番号をその番号と組み合わせるべきだ」と考えました。 位置は？」

1. 次に、これらのペアを値で並べ替えることができます (つまり、 各ペアの最初の番号)、しかし私たちは追跡しています 彼らはどこから来たのか (それが 2 番目の数字です)!

1. ここからがすごいところです - これらのうち k 個だけが必要なので、 最初の k 個のペアを作成し、その位置を維持するだけです:

1. 最後に、元の配列を調べて、のみを保持します セット内の位置にある番号:

コードは次のとおりです

2: ストリーム内の K 番目に大きい要素

わかりました。これも (5 社に依頼して) 「簡単」とラベル付けされていますが、私にとっては、より難しい K 番目の要素の問題よりも混乱しました。

彼らが尋ねていること

あなたが大学で働いていて、学生がテストのスコアを提出し続けていると想像してください。あなたの仕事は、いつでも k 番目に高いスコアを常に把握することです。新しいスコアが次々と追加されるので、追跡する必要があります。

彼らはあなたに k といくつかの初期スコアを与え、その後新しいスコアを投げ続け、毎回 k 番目に高いスコアを知りたがります。例を見てみましょう:

わかりました、分かったと思います

最初は、新しいスコアが入るたびに配列全体をソートしようと試み続けましたが、ソートが非効率であることはわかっています。それから、上位 k 位だけを気にしているのに、なぜすべてのスコアを追跡しているのかと考えました。

これをどのように分解したかを次に示します。

1. まず、初期スコアを並べ替えて、上位 k 個だけを保持します。

1. 新しいスコアが入ったら:

k 番目に大きい値 (最初の数値) より小さい場合は、無視します
それより大きい場合は、リストのどこかに含まれます

各追加で何が起こっているかは次のとおりです:

コード

これら 2 つの問題が関連している理由

どちらの問題も、k 個の要素の処理に関して非常に重要なことを教えてくれました。

• 最初の問題: 要素がどこにあるかを追跡する必要がある場合があります。
から来ました
• 2 番目の問題: k 個の要素だけを保持する必要がある場合がある
あたり

これらの k 要素の問題は、どの情報を保持し、何を捨てるかを賢くすることに関するものです。
次回は、これらのアイデアに基づいたさらに 2 つの k 要素の問題を見ていきます。最後にはパターンが見えてきて、この種の問題がそれほど怖くなくなることを願っています!

以上がLeetCode の K 要素パターンを理解する: 基本 (パート 1)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。