Skip to main content

如何练习

那些最成功的问题解决者都是先花费精力确认他们面临的到底是哪一类的问题，然后再找到相对应的解决策略，而不是直接跳进那些已经烂熟于心的程序或步骤里。

算法练习中，我们首先学习如何高效练习，然后再花大量时间在算法练习上。

练习的原则​

练习需要按照 3F 原则进行练习，也就是 Focus（专注），Feedback（反馈），Fix（修正）

  • Focus：两小时的 100% 专注比四个小时的 80% 专注效果要好，我们建议每天固定算法练习的时间段，例如每天上午 10 点到 12 点，将其当成与吃饭同样重要的事情来安排行程，并通过长时间的坚持来养成习惯。
  • Feedback： 像前期准备中提到，你需要避免天真的练习，而是需要从每天的练习中获得反馈，知道自己哪些知识点没有掌握，哪些地方不熟练，并且进行针对性地练习。通常来说，你需要找一位导师或者更有经验的工程师在模拟面试中为你提供反馈。
  • Fix：通过反馈知道自己不足之处，就可以针对性地进行练习，在知识点你可以看到具体的知识点以及练习内容。

设定正确的计划​

“我们都有一个不健康的习惯，那便是：制订结果目标（也就是反映我们计划中的结果），而不是专注于达到那一结果的过程。这在我们日常生活中的许多活动上表现得十分明显。我们将视线转向计划中的目标，完全忽略了在实现目标过程中享受当下的每一刻。我们错误地认为，我们终于实现目标的那一神奇时刻到来之时，我们会感到很愉快。我们把实现目标的过程，几乎视为实现目标而必须经历的麻烦事。” - 《练习的心态：如何培养耐心，专注和自律》

我们以正念为例，正念是一个不错的放松方法。初学者可能会先设定时间指标的计划，例如每天正念五分钟，然后慢慢增长时间。但是这种以时间为导向，只关注单一指标的计划是有偏差的，过程要比结果更为重要。原因如下：

  1. 对于刚接触正念的初学者，闭上眼睛的时候会感受思绪万千，五分钟的时间也如坐针毡。仅仅以时间为指标会让他们陷入效率，想着怎么还没到时间，是不是我的心不够定，是不是我想得太多。这与正念的初衷背道而驰。
  2. 时间只是正念质量的其中一个指标，仅仅关注这个指标的话，可能会误以为越久越好，或者达到一定的时间就可以，没有真正去掌握正念的其他要素。

一个正确的计划应该包含更多的指标：

  1. 在正念的过程中尽量放松自己
  2. 如果脑海出现许多想法的话尝试专注在呼吸上
  3. 尝试坚持五分钟

这个计划看似与时间指标的计划没什么区别，但是它将在正念过程中克服内心的焦躁与天马星空这点包含到练习计划的内容当中，而这才是正念的真正目标。之前时间指标的计划会将这部分当成浪费精力与时间，也是导致你焦躁不安的原因。

对于算法练习来说，常见的有偏差的计划是：每天完成 10 道题目。如果你的计划是完成 10 道题目，那么在做题的过程中，你会仅仅以是否完成题目为目的。这会导致几个问题：

  1. 有的题目它有多种解法，每种解法都对应着不同的知识点，能够从不同的角度帮助你提高算法能力。但是当你以完成题目为目的，那么在完成第一种解法之后，你往往会缺乏使用多种解法的动力，也就错过了算法提升的机会。
  2. 你可能因为完成了题目而误以为自己已经掌握了该题，实际上，你只是掌握了该题的其中一个解法。
  3. 当你做题的过程中遇到挫折的时候，容易会陷于懊恼与自我怀疑中，即使你在一道题中学习到很多有用的算法知识，但是由于你的目标是完成题目而不是学习知识，你会觉得自己浪费了时间，也就没有得到应该的正反馈。

以题目数量为计划的导向下，你很难享受做题的过程，因为评判标准只有完成以及没有完成，并没有真正反映出你是否得到提升。你可以将完成的题目数量，每周竞赛做出的题目数量当成一个评判算法水平的指标，但是不应该将其设定为计划。

正确的计划：完成 X 道二叉树习题，每道题目需要利用以下指标来检查自己是否掌握：

  1. 做题时间：如果你清楚自己大概的做题时间的话，那么在面试中就不会那么紧张，同时能够有更多的时间进行前期的分析以及思考。
  2. 通过测试用例：这是最基本的要求，代表代码能够在限制时间和内存内通过测试
  3. 正确分析时空复杂度：分析时空复杂度能够帮助你完理解程序的运行流程以及方式，能够在脑海中形成更加清晰的思路。面试中也会被问到。
  4. 能用两个解法解题：强制要求你从不同角度去观察与分析题目，可以帮助你熟悉不同类型题目的常见解法以及模式。
  5. 减少三行代码并通过：减少代码，要求你重新思考代码冗余的地方以及学习如何更好地运用编程语言的数据结构以及 API。
  6. 设计并完成 follow up（高阶要求）：在真实面试中往往会有 follow up，如果你在完成题目后能够通过修改一些条件来设计 follow up，不仅能够对题目有更深的理解，同时也能为面试的 follow up 做准备。
  7. 三天后 15 分钟内能够通过：有的题目你可能当天无法自己解答，需要看题解或者通过讨论，那么三天后再次做的话就能检查是不是真正掌握。
  8. 一个月后 15 分钟内能够通过：有的题目你可能当天无法自己解答，需要看题解或者通过讨论，那么一个月后再次做的话就能检查是不是真正掌握。

练习的方法​

富兰克林在练习写作的时候，发现自己一个关键的问题，他的词汇积累并不像《观察家》的投稿者那样丰富。并不是说他不认识那些词，而是他无法做到在写作时“文思泉涌、信手拈来”。为弥补这一不足，他想出了前一种练习的变体。他确定，写诗将迫使他想出大量其他不同的词语，他通常不会想到那些词语，只有在需要与诗歌的韵律和声律模式相一致时，才会去努力搜寻它们。因此，他找到《观察家》杂志上的一些文章，并将它们改写成诗句。接下来，在等待了足够长的时间，以至于最初记下来的诗句和措辞在他的记忆中已经消失时，他再把诗句改写成散文。这使他形成了一个习惯，就是要找到正确的词汇，并且增加对词汇数量的积累，以至于他可以迅速从记忆中调用这些词汇。- 《刻意练习：如何从新手到大师》

开始之前​

选择合适的题目

最好的题目应该是刚好超过你的舒适区，对你来说不会太简单或者太难，你可以按照 tag 以及出现频率进行选题，每个 tag 控制在 10 题以内，其中难度比例大概在：简单 5：中等 3：困难 2。

记录时间

根据题目难度，设定倒计时（简单：10 分钟，中等：20 分钟，困难：30 分钟）并且分阶段记录时间，方便更好观察耗时的地方，记录方式如下：

  1. 能够独立解答题目：

    1. 阅读题目到开始写代码的时间，例如 15
    2. 写代码到通过测试用例的时间，例如 5，最终记录形式为Pass 15 + 5。

  2. 无法独立解答：

    1. 阅读题目到无法解答的时间，通常少于 30 分钟，例如 25
    2. 阅读题解，理解后编码通过测试用例时间，例如 20，最终记录形式为 failed 25 + 20
note

Chrome 可以使用 Count Down Timer 插件来帮助计时

练习过程​

  1. 提出合适的 testcase

不同的算法练习平台可能预先已经给了一些例子，导致你会依赖练习平台来帮你理解问题以及考虑边界情况，但是在面试中，面试官并不会给出太多 testcase，你需要自己提出合适的 testcase。在练习最开始，你应该尝试提出一个 testcase。这个 testcase 需要在特殊性与一般性中取得平衡，尽量使用简单的 testcase 覆盖题目涵盖的所有情况。你可以通过不同的算法练习平台中的 testcase 以及提交后无法通过的 testcase 中学习怎样是合适的 testcase。

  1. 先分类，再实现

那些最成功的问题解决者都是先花费精力确认他们面临的到底是哪一类的问题，然后再找到相对应的解决策略，而不是直接跳进那些已经烂熟于心的程序或步骤里。

对一道题目，先区分题目的对应类别，再使用该类别的策略解决问题，例如二分查找的题目可以尝试使用 lower_bound 以及 upper_bound 这两个 API 来解题。

  1. 每道题目最多花费 1 小时

不要在一道题目中耗费 4，5 个小时，有的题目的最优解需要耗费极多时间，对于准备面试来说效率并不高。每道题目最多使用 30 分钟进行思考，如果超过 30 分钟没有解决的话，那么应该用剩下的 30 分钟阅读和学习题解（国区官方题解有一定的阅读门槛，但是质量颇高）在理解思路之后尝试实现题解并且对比代码。如果 1 小时无法完成练习的话，那么代表这道题对于你来说太难了，应该先尝试更简单的题目。

  1. 思路，注释，时空复杂度，计时缺一不可

对于题目 Two Sum

# 时间复杂度：O(n^2)
# 空间复杂度：O(1)
# 耗时：Pass 15 + 5
# 思路 1 ：使用两重循环，找到所有可能的组合，然后判断它们的和是否等于 target
class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
    n = len(nums)
    # 找第一个元素
    for i in range(n):
        # 找第二个元素
        for j in range(i + 1, n):
            # 判断是否等于 target
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

练习之后​

回顾总结​

学生之间的差别，在很大程度上最有可能取决于他们能多敏锐地察觉自己所犯的错误。 回顾和总结或许是最重要也最被忽略的一步。

如果你无法顺利解答题目，那么回顾这道题无法顺利解答的原因，可能的原因：

  1. 无法正确地进行分类，不知道是什么类别的题目。
  2. 知道分类后无法正确地套用对应的模版或者解题模式
  3. 无法将原问题分解成几个简单的子问题
  4. 无法想到相似的题目

总结包括几个方面，每做完一题，你可以尝试问自己几个问题：

  1. 从哪些地方（题目描述，数据输入），你可以猜测出这题可以使用哪些解法？（堆，动态规划）
  2. 解法中用到的数据结构，你了解它们在本题中的使用场景吗？为什么它们适用于本题？
  3. 你能将本题划分为几个小的知识点，然后逐个检查自己是否掌握了吗？

《计算机科学中的数学》给出了数学证明中回顾的要点，在算法题也十分适用：

  • 陈述计划：好的解题方案通常可以从一般性的解法开始，例如：我们可以使用递归来解决这个问题，我们可以使用分治来解决这个问题。
  • 步骤清晰：按照固定的顺序解题，例如从整体到局部，从上到下。切忌在不同的子问题中随意跳转。
  • 证明是短文而不是计算：解题过程应该能给面试官看到思路以及清晰的步骤，而不是将一堆代码和数字进行堆砌
  • 避免过度抽象：用具体的例子或者图表来解释思路，而不是使用抽象的前一个节点，下一个节点
  • 修改和简化：写完之后，可以对代码进行简化吗？
  • 深思熟虑地引入变量：需要那么多变量吗？变量命名规范吗？
  • 代码架构：如果代码复杂的话，如何建立合理的架构？
  • 小心显而易见的结论：有些结论虽然你觉得显而易见，但是面试官不一定觉得。另外，切忌用显而易见这几个字来掩盖你无法证明这个命题的事实。

学习大师的代码​

我们需要从大师的代码中学习如何写高质量的代码，除了从 Google Coding Style Guide 这样的一般性文档之外，对于每道算法题，我们可以浏览国区以及美区的前几个题解。要记住，你的计划是掌握知识点而不是完成题目，所以你可以有耐心以及时间去阅读以及消化这些代码。尝试从代码中学习不同的技巧，并且改进自己的代码。先花一些时间学习常见的编程语言 Java, C++, Python 的语法，即使有些题解没有你熟悉的语言，也不影响你学习它的思路。

记录练习过的题目​

使用软件记录练习过的题目以及完成的指标，一方面可以更好地了解自己的进度，同时也方便之后的复习。

学会观察​

以下为一位学员的代码，你可以观察代码中出现的问题：

algorithm code review

以下为面试官观察到的问题：

  • 第 5 行：逗号之间要有空格： lremove, rremove 缺乏空格
  • 第 6 行：i 一般指的是索引，不要用 for i in s 用 for c in s 都好一点
  • 第 10 行：为了可读性，if else 最好是用单独的行
  • 第 15 行：isValid 注意命名大小写规范，子函数最好提前定义好，直接放在主函数下面，不要中途才定义
  • 第 15 行：对于 Python 来说，str 不是一个特别好的变量名，因为有 str 函数
  • 第 20 行：if 与 elif 的用法不一致，这里用了 elif 那么其实第 9 行也可以用
  • 第 23 行：改为 return cnt == 0
  • 第 25 行：命名有点问题，为什么叫 cur，看不出指的是索引，同样缺乏空格
  • 第 31 行：可以删除此行，直接 isvalid(self, ss) 就好
  • 第39 和 第41 行，关键错误：用 ss 而不是 s，可以看出，正确的命名可以减少错误，你这里的问题主要是命名导致的混乱

里面有些问题比较重要，有些则无伤大雅，你在阅读其他人的代码以及自己写代码的过程中，学习观察问题，这样才能避免自己在写代码时犯同样的错误。另外也可以通过模拟面试帮助你发现问题。

分解知识点​

如果你觉得自己没有掌握某种类型的题目，可以尝试分解题目的知识点。以动态规划为例，你可以尝试问自己几个问题：

你知道在什么时候使用它吗？

如果你不知道什么时候需要使用动态规划，代表你不理解动态规划的概念以及使用场景，这时候仅仅通过做题并不能掌握此知识点，你需要通过阅读资料学习动态规划的概念，使用场景，优缺点以及常规的实现方式。

你知道它的解题步骤吗？

对于每个类型的算法，你应该对其解题步骤有清楚的了解，《算法导论》对动态规划的步骤有清晰的讲解：

我们通常按如下 4 个步骤来设计一个动态规划算法：

  1. 刻画一个最优解的结构特征。
  2. 递归地定义最优解的值。
  3. 计算最优解的值，通常采用自底向上的方法。
  4. 利用计算出的信息构造一个最优解。

步骤 1~3 是动态规划算法求解问题的基础。如果我们仅仅需要一个最优解的值，而非解本身， 可以忽略步骤4。如果确实要做步骤 4，有时就需要在执行步骤 3 的过程中维护一些额外信息，以便用来构造一个最优解。

学习这些步骤，并且在解题过程中严格按照步骤来分析与解题，能够保证你在正确的方向上。同样地，你需要阅读资料进行学习。

你知道它的难点吗？

动态规划的难点在于找到状态转移方程，如果你发现你解不出动态规划的题目是因为没有找到状态转移方程的话。可以通过总结状态转移方程的常见类型，从而掌握此知识点。常见的状态转移方程有以下几种（其中 A, B, C 为常数）：

形式类型
F(i) = A * F(i-1) + BF(i) 与 F(i-1) 有关
F(i) = A * F(i-1) + B * F(i-2) + CF(i) 与 F(i-1), F(i-2) 有关
F(i) = A * F(k) + B (0 < k < i)F(i) 与 F(k) 相关
F(i, j) = A * F(i-1, j) + B * F(i, j-1) + C * F(i-1, j-1)F(i, j) 与 F(i-1, j), F(i, j-1), F(i-1, j-1) 相关

你知道它的实现细节吗？

有的时候，你明明了解它的原理，但是怎么写都写不对，这时候，问题可能不是在动态规划这个知识点上，而在在编程语言的运用或者一般性的知识点上，例如一道二维动态规划的题目中，你写不对的原因可能是不熟悉二位矩阵的遍历以及更新，那么这时候你应该针对矩阵操作进行练习。