トーク・ウィズ・ユー シリーズ #1

**カバー画像は投稿時の雰囲気を反映しています

考えから始めたいのですが、しばらくの間、私には仕事の一部であれ、自由時間の活動であれ、日常的に直面していた課題とその潜在的な解決策を書き留める習慣があるということです。

この投稿から、「Talk with You」シリーズを紹介することにしました。ここに投稿して (少なくとも今のところ、多くても数日に 1 回)、一般公開することにします。

一方では、私は情報を修正するためによく構造化されたメモの代わりに時々ここを覗いて、DevCommunity がストレージ、昇順でのナビゲーション、その他すべてのものを処理するつもりですが、もう一方では、私は物事を信じています私がここに書いていることは、読者が私だけを代表して書いているわけではないと思われるかもしれません。しっかりして、キックオフしましょう。

出現回数を数える

DS を使用する場合、効率的な方法 (できれば O(1)) でクエリを実行するために、値とアフターワードの出現回数をカウントする必要があることがよくあります。

当然、HashTable を作成してから DS を走査し、HashTable に値を設定することを考えるかもしれません。それは真実であり、次のようになります:

iterable = [...]
hashtable = {}
for value in iterable:
    hashtable[value] = hashtable.get(value, 0) + 1

今日私は、HashTable の使用を避けて数字のリストを完全に機能させる代替アプローチに直面しました (場合によってはそれが必要になる場合もあります)。

背後にある考え方は、まずリストから最大値を取得し、インデックス マッピングとして使用される最大値の長さの新しいリストを作成することです。

list_ = [1, 1, 2, 3]
max_ = max(list_)
indices = [0] * max_   # [0, 0, 0, 0]

次に、元のリストを調べて、インデックス リスト内の各値の出現をマップしましょう。

1. iteration
[1, 1, 2, 3] # list
 |

[0, 1, 0, 0] # indices

2. iteration
[1, 1, 2, 3] # list
    |

[0, 2, 0, 0] # indices

3. iteration
[1, 1, 2, 3] # list
       |

[0, 2, 1, 0] # indices

4. iteration
[1, 1, 2, 3] # list
          |

[0, 2, 1, 1] # indices

何が起こったのですか。基本的に、元のリストから値を取得し、それをインデックス リストのインデックスとして使用しました (そしてインデックスの値を増加させました)。

マッピング リストを使用して結果を表現したい場合、インデックス 0 には値 0 があり、インデックス 1 には値 2 があるため、ゼロは 0 個あります。つまり、1 が 2 つあると言えます。 -s、インデックス 2 には値 1 があり、two-s が 1 つあることを意味します。

マトリックスのミラー要素

理学士と修士の学位を 2 つ持っているにもかかわらず、新しい数学のトリックを見つけると、「おお、それはとても簡単で効果的だ」という魅力的な感情が今でも得られます。

さて、本題に戻ります。N*N の行列があり、すべての要素の最大合計を (行ごとに) 取得するには、行と列を反転する必要があるとします。

matrix 4*4

1 2 3 9
0 9 8 2
5 1 7 4
8 2 6 7  

初めて見ただけでは、どこから始めればよいのかさえわからないかもしれません。ただし、ミラー化された要素を使用するトリックは次のとおりです。

matrix 4*4

A B B A
C D D C
C D D C 
A B B A

ここでの重要な点は、行列内の A は別の A によってのみ交換される可能性があるということです。私たちが左上隅 A (1) にいて、さらに大きい別の A (ミラー化された A のみ) があるかどうかを知りたいとします。そして実際、右上隅 (9) にそのようなものがあります。

ロジックに従い、元の問題 (行と列を反転する最大合計) を思い出すと、実際には逆の操作を実行する必要はなく、代わりにミラーリングされたものの中で最大値を検索するだけであると結論付けることができます。以上です。

スタック。時間と空間の複雑さの間のトレードオフ。

3 つの機能 (1) ポップ (2) プッシュ (3) get_min のみを備えたスタック ラッパーを実装するタスクがあるとします。 (1) ポップと (2) プッシュにはスタックのインターフェイスを使用できますが、それでも (3) get_min を実装する必要があります。 Annnd get_min() は O(1) 時間の間機能するはずです。

そうですね、最初にこの問題に取り組んでいたとき、私はトレードオフのことをすっかり忘れていました。「時間のパフォーマンスを最適化すると、スペースのパフォーマンスはおそらく悪化し、賢明な場合はその逆です。」なぜそれが重要なのかというと、最適化された DS について考え始めて HashTables に行き着いたのですが、O(1) (償却) にも機能する可能性のある単純なリストを本当に見逃していたからです。

そこで、ラッパー クラスの各状態を保存する HashTable を作成する段階に到達しました。(場合によっては)「シンプルな方が良いオプション」であるため、ここで終了します。スタックの各状態の最小値を保存する追加リストを含む実装を見てみましょう。

class Wrapper:
   def __init__(self, stack):
      self.stack = stack
      self.min = []

   # Time O(1)
   def pop(self):
      self.stack.pop()
      self.min.pop()

   # Time O(1)
   def push(self, value):
      self.stack.push(value=value)
      min_ = self.min[-1]
      if value < min_:
          min_ = value
      self.min.append(min_)

   # Time O(1)
   def get_min(self):
      return self.min[-1]

とにかくシンプルです。

結論

• コーディングと開発を続けてください
• トレードオフについて覚えておいて、（質問されない場合は）過度に複雑にしないでください

以上がトーク・ウィズ・ユー シリーズ #1の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。