你有。 松了一口气。 累。 你终于想出了一种方法来解决面试官问你的棘手的编码问题。 也许你甚至一行一行地在白板上写下来。 你玩的很开心！ 你进入会议只有20分钟。 你的面试官必须留下深刻的印象。
对？
“这会起作用，但有关如何更有效地实现这一目标的任何想法？”
你的心在下沉。 你以为你已经完成了棘手的算法设计部分！ 你试着想出更多解决问题的方法，但你能想到的只是你已经提出的一种方法。
这几乎发生在每个人身上。 并不是因为他们是愚蠢的。 这是因为大多数人没有提高算法效率的方法。
但事实是，有很多。 下次你难倒，尝试应用这三种常用方法。
1.使用哈希地图
那就对了。 散列图/关联数组/字典（它们有许多名称，取决于您正在使用的编程语言）具有降低算法运行时的神奇能力。
例如，假设问题是在数组中找到重复次数最多的数字。
你的第一个想法可能是跳进一些循环。 对于我们的每个数字，计算出它的数量，看看它是否是最大的数字。 我们如何得到每个数字的计数？ 循环遍历数组，计算它发生的次数！ 所以我们讨论的是两个嵌套循环。 在伪代码中：
def get_mode（nums）：max_count = 0 mode = null for nums中的potential_mode：count = 0表示our_array中的数字：count + = 1 if count> = max_count：mode = potential_mode max_count = count return mode
现在，我们为阵列中的每个项目循环遍历整个数组 - 但我们可以做得更好。 在大O符号中，总共是O（n 2 ）时间。
如果我们将计数存储在哈希映射中（将数字映射到它们的计数），我们只需一次遍历数组即可解决问题（O（n）time！）：
def get_mode（nums）：max_count = 0 mode = null counts = new HashMap，为n中的potential_mode启动每个值为0：如果计数> max_count，则计数+ = 1：mode = potential_mode max_count =计数返回模式
快多了！
2.使用位操作
这真的让你与众不同。 它并不适用于所有问题，但是如果你把它放在后面的口袋里并在正确的时间将其破坏，你就会看起来像摇滚明星。
这是一个例子：假设我们有一个数字数组，每个数字出现两次，除了一个只出现一次的数字。 我们正在写一个函数来找到孤独的，不重复的数字。
你的第一直觉可能是使用哈希映射，因为我们只是谈论它。 这是一种很好的直觉！ 它会适用于这个。 我们可以制作一个非常相似的“计数”地图，并使用它来查看哪个数字最终为1。
但是还有更好的方法。 如果您熟悉位操作，则可能熟悉XOR。 关于XOR的一个特别之处在于，如果你对一个数字进行异或，则“取消”为0。对于这个问题，如果我们对数组中的每个数字进行异或，我们将留下一个数字取消：
def find_unrepeated（nums）：unrepeated = 0表示num中的num：unrepeated = unpeated XOR num return unrepeated
3.自下而上
编写一个输出“nth”Fibonacci数的函数，给定数字n。 这是一个经典之作，它非常适合递归：
def fib（n）：如果n为0或1：返回1返回fib（n-1）+ fib（n-2）
但简单的递归答案并不是唯一的答案！ 仔细考虑这个功能的作用。 假设n是5.为了得到答案，它递归地调用fib（4）和fib（3）。 现在，这对fib（4）的作用是什么？ 它称为fib（3）和fib（2）。 但我们刚刚说过我们已经调用了fib（3）！ 这个可爱的递归功能做了很多重复工作。 总时间成本为O（2 n ）。 这比O（n 2 ）差。
我们不是从递归地递减到1，而是从“自下而上”，从1到n。 这让我们跳过递归：
def fib（n）：previous = 0 previous_previous = 1表示i在1到n范围内：current = previous + previous_previous previous_previous = previous previous = current return current
代码更长，但效率更高！ 低至O（n）时间。 作为展开递归算法的额外好处，我们节省了空间。 所有这些递归调用都在调用堆栈中构建，调用堆栈位于内存中并计入我们的空间成本。 我们的递归函数有一个O（n）空间成本，但是这个迭代函数需要O（1）空间。
下次您的面试官要求您提高解决方案的效率时，请尝试逐步完成这些策略，看看它们是否有帮助。 通过足够的练习，您可能会发现自己直接跳到优化的解决方案，跳过更天真的解决方案。 这是一件好事。 这并不仅仅意味着你成为一名更好的面试官 - 这意味着你正在成为一名更好的工程师。
