トーク・ウィズ・ユーシリーズ #1-Python チュートリアル-php.cn

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

WBOY

リリース： 2024-07-16 09:23:09

オリジナル

1054 人が閲覧しました

Talk with You Series #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

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]

ログイン後にコピー

とにかくシンプルです。

結論