効率的な方法を見つける

皆さん、こんにちは！今日は LeetCode の 3 つの問題、Unique Paths、Spiral Matrix、N-Queens を解決しました。これらの問題を見ていきましょう。

一意のパスの問題

行数と列数を表す 2 つの数値が与えられます。私たちのタスクは、(0,0) から位置 (m-1,n-1) に到達する一意のパスの総数を見つけることです。この問題を解決するには、再帰的アプローチに従うことができます。 (0,0) から開始して、必要な位置に到達するまで右と下に移動するステップを再帰的に見つけることができます。合計の一意のパスを見つけるには、正しいステップを一番下のステップに追加して返します。ただし、このアプローチには小さな問題があります。解決策が何度も繰り返される可能性があります。これを克服するための代替アプローチは、DP マトリックスを使用することです。入力と同じ行数と列数を持つ DP 行列を作成し、DP 行列のすべての位置を 1 で初期化します。最後に、DP 行列の緯度セルの値を一意のパスの合計数として返します。

スパイラルマトリックス

行列が与えられているので、行列の要素をらせん状に含むリストを返さなければなりません。この問題を解決するには、ループを実行する条件としてインデックス作成の制限を使用します。行列の左から右にトラバースし、for ループを使用します。次に、別のループで右上隅から右下隅に移動します。 3 番目のループを使用して、右下隅から左下隅までトラバースします。最後に、4 番目のループで左下隅から左上隅に移動します。このようにして、4 つの異なるループを使用して 4 方向すべてに移動し、インデックス制限で制御します。

N-クイーンズ

入力数 n が与えられているので、2 つのクイーンが互いに攻撃しないように n 個のクイーンを nxn 行列に配置する方法の数を見つける必要があります。これは、2 つのクイーンが同じ行、列、または対角線上にあってはいけないことを意味します。この問題を解決するには、再帰とバックトラッキングの概念を使用できます。まず再帰を実行してプロセスを複数回繰り返すことができます。なぜなら、クイーンを配置する可能なすべての方法を見つける必要があるからです。クイーンを配置するための正しい位置が見つからなかった場合、バックトラッキングが実行されます。その後、「Q」を「.」に置き換えて、次の位置に対してプロセスを繰り返すことができます。

3 つのリストを使用して、上記のソリューションを最適化できます。リストの 1 つは、行数を追跡することです。 n 行があるとします。リストに n 個のゼロを配置し、その特定の行にクイーンがある場合は、それぞれのゼロを 1 に置き換えます。これにより、不必要な後戻りを避けることができます。同様に、2 番目のリストは下側の対角線用であり、3 番目のリストは上側の対角線用です。両方の対角リストには 2n-1 個の要素があり、最初はすべてゼロに設定されます。行列をたどってクイーンを配置すると、クイーンが配置されるときに 0 を 1 に置き換えて、それぞれの行または対角リストを更新します。これは、その対角線または行にそれ以上クイーンを配置できないことを示します。このようにして、このアプローチは効率的に機能します。

私の経験がお役に立てば幸いです。

以上が効率的な方法を見つけるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。