coding-interview-techniques

id: 编码面试技巧  
title: 面对并解决编码面试问题的顶级技巧  
description: 学习寻找编码面试问题解决方案的方法，并优化其时间和空间复杂度  
keywords:  
  [
    如何应对编码面试问题,  
    如何解决任何编码面试问题,  
    编码面试练习,  
    编码面试问题,  
    优化时间复杂度,  
    优化空间复杂度,  
    优化时间和空间复杂度,  
  ]  
sidebar_label: 解决问题的技巧​

import InDocAd from './_components/InDocAd';

大多数候选人参加编码面试时最大的恐惧是：如果我卡在题目上，不知道该怎么解怎么办？幸运的是，有一些结构化的方法可以用来应对编码面试问题，从而提高你解题的成功率。从如何找到解法或思路，到优化时间和空间复杂度，以下是一些顶级技巧和最佳实践，能帮助你轻松解决编码面试问题。

如何找到编码面试问题的解决方案

当拿到一道编码面试题时，候选人应首先提出一些澄清问题，并与面试官讨论几种可能的解题思路。然而，这也是大多数候选人容易陷入困境的地方。好在，我们有办法以一种结构化的方式来处理这些问题。

需要注意的是，并非所有技巧都适用于每一道编码面试题，而且你甚至可以在同一道题中同时运用多种技巧！当你在练习过程中逐步应用这些技巧时，你会逐渐培养出直觉，知道哪种技巧最适合当前的问题。

1. 通过画图来可视化问题

你有没有想过，为什么传统的编码面试都是在白板上进行的？而讲解编码问题的视频里也经常用图表来解释答案？白板便于画图，这有助于解题！编码的一大关键在于理解程序内部状态是如何变化的，而图表正是表示内部数据结构状态的超级有用工具。如果你很难理解解题过程，不妨试着画出问题的可视化图示，必要时还可以画出每一步的内部状态。

这个技巧尤其适用于输入涉及树、图、矩阵、链表的问题。

示例

如何按螺旋顺序返回矩阵的所有元素？画出矩阵以及迭代器在每个方向上需要走的步骤，会极大地帮助你发现其中的规律。

2. 想象自己用手解题

用手解题就是不写代码地解决问题，就像一个非程序员那样思考。其实，当你试图理解给定的例子时，这种做法大部分时候已经自然而然地发生了。

有些人没意识到的是，有时候一个可行的解法其实就是手解方法的代码版本。如果你能为某种解法总结出一套明确的规则，让它适用于所有例子，那么就可以把这套规则写成代码。虽然这样未必能得到最高效的解法，但至少是个不错的开始，能为你赢得一些分数。

示例

如何验证一棵树是否为有效的二叉搜索树而不写代码？首先检查左子树中的值是否都小于根节点，然后检查右子树中的值是否都大于根节点，再对每个节点重复这个过程。这个思路看起来很可行。现在你只需要把这个过程转化为代码。

3. 多举几个例子

多举几个例子是一件无论你卡住与否都很有用的事情。它能帮你强化对题目的理解，避免过早进入编码阶段，还能帮你找出一种模式，这种模式可以推广到任意输入，也就是最终的解法！最后，多个例子还能在验证你的解法时作为测试用例。

4. 把问题分解成更小的独立部分

如果问题规模较大，可以从一个高层次的函数入手，把它分解成若干个更小的函数，分别解决它们。这样可以避免一下子被细节压垮，让你的思路保持清晰。

这样做也能让面试官清楚地看到你有一个解题思路，即使你没能完成所有小函数的编码。

示例

分组字母异位词这个问题可以分解成两个部分——对字符串进行哈希，然后把字符串分组。这两个部分可以分别解决，各自有不同的实现细节。你可以先从这段代码开始：

def group_anagrams(strings):
  def hash(string):
    # Fill in later
    pass

  def group_strings(strings_hashes):
    # Fill in later
    pass

  strings_hashes = [(string, hash(string)) for string in strings]
  return group_strings(strings_hashes)
​

然后逐步填充每个函数的实现。不过要注意，有时候最高效的解法可能需要打破一些抽象，一次遍历输入就能完成多个操作。如果你的面试官要求你基于已有的抽象解法进行优化，那也是一种可行的方向。

5. 在问题中应用常见的数据结构和算法

与现实世界软件工程不同，现实世界的软件工程问题通常是开放式的，可能没有明确的解法；而编码面试题则往往规模较小，设计成能在面试时间内解决。你也可以预期，解决这些问题所需的知识并不超出常规范围，应该是在大学里学过的。幸运的是，常见的数据结构和算法数量有限，根据我的经验，一个比较“笨”的方法就是尝试遍历所有常见的数据结构，然后把它们应用到问题中。

以下是需要记住并尝试的数据结构，按照它们在编码面试题中出现的频率排序：

• 哈希表：用于高效查找。这是面试中最常用的数据结构，你几乎肯定要用到它。
• 图：如果数据是以实体之间的关联形式呈现的，你可能会把问题建模成图，然后用一些常见的图算法来解题。
• 栈和队列：如果你需要解析包含嵌套属性的字符串（比如数学表达式），几乎肯定要用到栈。
• 堆：问题涉及基于某种优先级的调度或排序。也适用于在集合中查找最大K个/最小K个/中位数元素。
• 树/前缀树：你需要以节省空间的方式存储字符串，并且要非常快速地查找字符串的存在性（或者至少是字符串的一部分）？

常见算法：

• 排序
• 二分查找：如果输入数组已排序，你需要比O(n)更快地查找时很有用
• 滑动窗口
• 双指针
• 并查集
• BFS/DFS
• 从后往前遍历
• 拓扑排序

未来我们会补充更多技巧，教你如何更好地根据问题识别最相关数据结构和算法。

如何优化你的解题思路或方案

当你初步解决了编码面试问题后，面试官很可能会提示你优化解法，问：“我们能不能做得更好？”以下技巧能帮助你进一步优化解法的时间和空间复杂度：

如何优化时间复杂度

1. 确定解法的最佳理论时间复杂度

解法的最佳理论时间复杂度（BTTC）是你已知无法超越的时间复杂度。

举几个简单的例子：

• 找数组中数字之和的BTTC是O(n)，因为你至少要遍历数组里的每个值一次。
• 找字母异位词分组的数量的BTTC是O(nk)，其中n是单词数量，k是单词的最大字母数，因为你至少要遍历每个单词一次，还要遍历每个单词里的每个字符一次。
• 找矩阵中岛屿数量的BTTC是O(nm)，其中n是行数，m是列数，因为你至少要遍历矩阵里的每个单元格一次。

为什么要知道BTTC很重要？这样你就不会陷入寻找比BTTC还快的解法的误区。实际最快的解法永远只能达到BTTC的速度，不可能比BTTC更快。BTTC不一定能在实际中实现（所以叫“理论”），但它意味着你永远找不到比它更快的真正解法。如果你的初始解法比BTTC慢，就有可能通过改进达到BTTC（但并非总是如此）。向面试官提及BTTC并不会有什么坏处，反而会被视为积极信号，同时也能提醒你自己不要试图找到比BTTC还快的解法。

有些人可能会认为，BTTC只是数据结构中元素的总数，因为你要遍历每个元素一次。但这并不总是成立。最著名的例子就是在已排序的数组中找某个数。排序特性会让事情完全不一样：

• 找某个数的时间复杂度是O(log(n))，因为可以用二分查找。
• 找最大数的时间复杂度是O(1)，因为它是数组中的最后一个值。

这就是为什么一定要注意题目给出的每一个细节。小心别因为没注意题目细节而确定了错误的BTTC！

确定了正确的BTTC后，你就知道最优解法的时间复杂度介于你的初始解法和BTTC之间，可以朝着这个目标努力。如果你的解法已经达到BTTC，而面试官还要求你进一步优化，他们通常关注两点：

• 做更少的工作。你的解法可能是O(n)，但面试官希望你只遍历一次数组。
• 使用更少的空间。请参考下面关于优化空间复杂度的部分。

2. 找出重叠和重复计算

一个朴素的暴力解法往往会一遍又一遍地执行同样的操作。当代码正在做一项昂贵的操作，而之前已经做过时，不妨停下来想一想，能不能复用之前的计算结果。动态规划（DP）是最明显的可以充分利用过去计算结果的问题类型。也有一些非DP的问题也能利用这个技巧，虽然没那么直接，可能需要预处理步骤。

示例

数组中除自身外的乘积就是一个很好的例子，它包含了重叠和重复计算。要得到某个索引的值，你需要把其他所有位置的值相乘。如果对数组里的每个值都这么做，时间复杂度会是O(n²)。但是，注意：

• result[n] = Product(nums[0] … nums[n-1]) * Product(nums[n + 1] … nums[N - 1])
• result[n + 1] = Product(nums[0] … nums[n]) * Product(nums[n + 2] … nums[N - 1])
• result[n] = result[n + 1]
• 如果数组为空且长度为0
• x < 5 且 x < 10
• 如果 slow() 或 fast()
• true
• true
• fast()
• if likely() 和 unlikely()
• unlikely()
• false
• likely()
• length = len(array)
• length
• len(array)
• 每次需要的时候都调用。

提前终止

提前终止。一旦有了答案，立刻返回答案。这里有个利用提前终止的例子。考虑这样一个基础问题：“判断一个字符串数组中是否存在某个字符串，忽略大小写”。它的代码如下：

def contains_string(search_term, strings):
  result = False
  for string in strings:
    if string.lower() == search_term.lower():
      result = True
  return result
​

这段代码能用吗？当然能。但它是不是效率最高呢？不是。我们只需要知道搜索词是否存在于字符串数组中。一旦确认存在，就可以立即停止遍历。

def contains_string(search_term, strings):
  for string in strings:
    if string.lower() == search_term.lower():
      return True # Stop comparing the rest of the array/list because the result won't change.
  return False
​

大多数人其实都知道这一点，面试之外也会这么干。但在紧张的面试环境中，人们往往会忘记最明显的事。在循环中能提前终止的，就提前终止。

减少循环内的工作

让我们进一步改进上面的例子，解决“判断一个字符串数组中是否存在某个字符串，忽略大小写”的问题。

def contains_string(search_term, strings):
  for string in strings:
    if string.lower() == search_term.lower():
      return True
  return False
​

注意，你在调用 search_term.lower()，而这个调用在整个函数生命周期内都不会改变。

def contains_string(search_term, strings):
  search_term_lowercase = search_term.lower()
  for string in strings:
    if string.lower() == search_term_lowercase:
      return True
  return False
​

减少循环内的工作，不要重复做已经做过的事情，只要它没有变化。

懒惰求值

懒惰求值是一种求值策略，它会延迟表达式的求值，直到真正需要它的值。让我们用上面的例子来说明。实际上，我们可以稍微改进一下：

def contains_string(search_term, strings):
  if len(strings) == 0:
    return False
  # Don't have to change the search term to lower case if there are no strings at all.
  search_term_lowercase = search_term.lower()
  for string in strings:
    if string.lower() == search_term_lowercase:
      return True
  return False
​

这被认为是一个微优化，大部分时候，strings[nums[4]]。

2. 改变数据结构

又是数据结构！没错，又是数据结构！数据结构在编码面试中至关重要，掌握得好坏直接决定你的面试表现。你是不是用了最适合当前问题的数据结构？

示例

给你一个字符串列表，你想知道有多少个字符串以某个前缀开头。怎样高效地存储这些字符串，才能快速算出答案？前缀树是一种树状数据结构，非常适合存储字符串，还能快速计算有多少个字符串以某个前缀开头。

下一步

如果你还没看过，我建议你看看我的免费的编码面试结构化指南，里面包含了详细的步骤指导，比如：

• 如何为你的编码面试准备制定高效计划——包括根据剩余时间安排学习重点和题目
• 编码面试最佳实践速查表——包括面试时的行为准则，以便展现求职信号
• 算法速查表——包括每种数据结构必须牢记的关键点

免责声明：
本文档采用基于机器的 AI 翻译服务进行翻译。尽管我们力求准确，但请注意，自动翻译可能存在错误或不准确之处。应以原文语言版本的文档作为权威依据。如需获取关键信息，建议使用专业的人工翻译。对于因使用本翻译而产生的任何误解或误读，我们概不负责。