與你交談系列#1

**封面圖片反映了發佈時的心情

想從這樣的想法開始，有一段時間，我確實有一個習慣，寫下我每天遇到的挑戰及其潛在的解決方案，無論是我工作的一部分還是空閒時間活動。

從這篇文章開始，我決定推出「與你對話」系列，我會把它們發佈在這裡（至少現在，最多幾天一次），讓公眾發現它們。

一方面，現在我會時不時地瞥見這裡，而不是我結構良好的筆記來修改一些信息，DevCommunity 將處理存儲、升序導航和所有其他內容，另一方面，我相信這些事情我寫到這裡可能會發現讀者不只代表我。係好，我們開始吧。

計數出現次數

在使用 DS 時，您經常需要計算值和後記的出現次數，以便以有效的方式查詢它們，最好是時間 O(1)。

顯然，你可能會想到創建HashTable，然後遍歷DS，填充HashTable。這是真的，可能看起來像：

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

今天我遇到了一種替代方法，可以完美地處理數字列表，從而避免使用哈希表（有時這可能是必要的）。

背後的想法是首先從列表中獲取最大值並創建一個新的最大值長度列表，該列表將用作索引映射。

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 處我們有值0，在索引1 處我們有值2，這意味著有2個1 -s，在索引2 處，我們的值為1，這意味著有1 個2-s，等等

矩陣中的鏡像元素

儘管擁有 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) pop (2) push (3) get_min。您可以使用堆疊介面進行（1）彈出和（2）推送，但仍然需要實作（3）get_min。 Annnd get_min() 應該在 O(1) 時間內工作。

嗯，當我第一次解決這個問題時，我完全忘記了一個權衡，它說：「當你優化時間性能時，空間性能可能會變得更糟，反之亦然」。為什麼它很重要，因為我開始考慮優化的 DS，它引導我使用 HashTables，但我真的很懷念樸素列表，它也可以用於 O(1)（攤銷）。

因此，當我建立一個雜湊表時，我可能會儲存包裝類別的每個狀態…將在此停止，因為「更簡單是更好的選擇」（有時）。讓我們看看使用附加列表來儲存堆疊每個狀態的最小值的實作。

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中文網其他相關文章！