原创声明

本公众号所有文章均原创，未经许可不得转载（已与维权骑士签约）。文章以图解为主、代码为辅。如果您感兴趣，欢迎关注！

文：吴潇/Java高级工程师

注：本文严禁转载，除非作者授权，侵权必定追究！

在LeetCode上面刷题，正确的解题步骤应该是什么样的？为什么有的人在LeetCode上面刷了好几百道题，甚至全部都刷完了，遇到没见过的题还是不会做？在LeetCode上面刷题，到底应该怎么做才能获得最大程度锻炼效果，提高自己的思维能力？今天这篇文章就是要帮助大家解决这些问题的。

相信很多程序员在找工作之前，都会到LeetCode去刷题，从而增加面试拿到offer的几率。LeetCode网站本身也是为算法面试量身定做的。我以前的几个同学，在毕业季到来前，已经把网站上所有题目刷了一遍，非常勤奋。

但是他们大多数人刷题的主要目标，是把各种题目全部熟悉一遍，达到各种问题都见过。他们认为，只要事先见过这一类题并且弄懂，下次再遇到这类题就直接会做了，算法面试就过关了。他们认为，遇到全新的问题而且能在短时间内把它解出来是非常困难的，面试时间那么短，怎么可能解得出来？只要刷完全部LeetCode题目，每次只要遇到算法题，基本上都是做过和见过的，那面试算法题就没问题了。

虽然他们最后差不多都拿到了不错的offer，但是个人觉得，这样的做法其实是一种题海战术，主要靠记忆力，而且违背了面试考察算法的初衷。以题海方式刷LeetCode，虽然也能在一定程度上提高思维能力，但是对于思维能力的提升很有限。一旦遇到新问题，往往又会被打回原形，看着题目想半天也不知道怎么下手。

要通过刷题来提升思维能力而不是大量刷题并且记住这些题目，这样收获才最大、对自己才最有用的，这也是谷歌、微软等公司面试考算法题的本意。那么怎样刷题才有锻炼效果呢？首先，尽量要做自己没有做过的题目；然后，按照本文给出的几个步骤，完成每一个步骤中的思考任务；最后，把每个步骤中得到的结论汇总起来，得出这道的最优解。解完题目以后，反思自己在思考过程中有哪些可以改进的地方，有哪些收获。以这种方式锻炼自己，日积月累，就能大大增强算法设计能力，谷歌、微软的offer岂不唾手可得。

我们就以LeetCode上的一道难度hard的算法题为例，演示解LeetCode算法题的大致过程，在这个过程中我们做了哪些思考，我们如何一步一步提出问题、分析问题，最后解决问题的。这个解题过程，不仅演示了我们的解法是怎么得来的，而且演示了如何利用好一道题目，让思维和能力真正得到锻炼。我故意找一道没有做过的题目，题目的名称为"Decode Ways II"。

在开始之前，需要明白我们自身满足什么条件才能解出一道题目来，这一点很重要。从宏观角度看，需要满足这3个条件。第1个条件是充分理解题目本身，例如输入是什么、输出是什么、有什么特殊条件等等，这里考验的是阅读能力和细心程度；第2个条件是完全掌握这道题所需要的知识，例如这道题需要用到分治法或动态规划等，那么你在解题之前必然需要掌握有关知识，否则即使想破脑袋也解不出来；第3个条件就是你把问题分析清楚，弄起其本质以后把它与解题知识建立起"连接"。它们之间的关系如下。

满足这3点要求就好比练武功打通任督二脉一样，解题就像呼吸一样自然。很多时候，我们解不出一道算法题，可能就是因为3个条件中的某一个不满足。假如条件1不满足，没有把问题弄懂，那结果可能是连暴力破解算法都设计不出来。例如，一个经典问题，"上一段楼梯，每次可以上1步台阶或2步台阶，台阶总数为n，问有多少种上楼梯的方法"。这个问题，你如果把它弄懂了，就知道它是一个f(n) = f(n-1) f(n-2)的问题，它就是一个Fibonacci数列问题。这样你后面才会知道如何用动态规划的方法解决这个问题。假如条件3不满足，那你无论思考多长时间肯定也解不出这道题目，这个时候说明你知识不够用了，需要停下来，把相关知识学会了，然后再来刷题。所以，假如有个问题卡主你很长时间，那很有可能是这道题涉及到的知识你真的不会。

如上所述，第一步当然是认真阅读题目。首先要仔细阅读题目，研究问题本身，抓住问题的关键点。这一步其实非常关键，但是经常被很多人忽略。很多题目，它的某些条件说明，对算法实现有非常大的影响。通过阅读题目捕捉关键条件是一项重要技能。读题目要确保准确、全面的理解问题。这个问题描述如下：