与你交谈系列#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中文网其他相关文章！