SimoneLeetCode 该如何刷题？
的有关信息介绍如下：
关于如何刷题这个问题，其实是一个老生常谈的话题了，在力扣君的主页（下方链接）分享了很多可供大家参考的方法论。
今天小编想跟大家分享一下刷算法题的特别技巧和思路。
众所周知，算法题主要有两大难点。
一是「实现」，即算法本身的难度。
二是「思路」，代表你能否想到使用这个算法来解决题目。
并且对于有一定刷题基础的同学来说，力扣上大部分简单、中等题所涉及的算法都是非常常见的算法，即算法本身不存在难度，最大的难点在于「思路」，即如何想到适合本题的算法。
而解决「思路」问题，除了大量刷题积累经验之外，还可以采用一定的「巧劲」，从时间复杂度这个角度入手筛选出合适的算法。本文的主要目的就是向大家介绍这种「巧劲」是如何在具体解题过程中发挥作用的，会分成三个部分带大家介绍～（码住收藏吧）
如何判断时间复杂度
如何确定一道题合适的时间复杂度？最简单、快捷的方式就是通过观察题目中的数据范围来确定。
不过你可能马上会反驳，力扣上并不是所有题目都有数据范围，那又该如何确定？在没有数据范围的情况下也可以采用这种方式来思考，我们会在后续「练习」部分进行详细说明。
言归正传，如何通过数据范围来确定合适的时间复杂度？
通常来说，在力扣上，Python 可以支持到 10*7 的时间复杂度；C++ 会稍微多一点，大概 10*7 - 10*8 之间。因此我们可以得到如下表所示的，数据范围与算法大致时间复杂度的对应表。
复杂度总结
此处有两点需要注意：
1. 上图仅列出了时间复杂度较为固定的常见算法，而类似于动态规划、贪心、暴力等时间复杂度百变多样的算法并未列出。
2. O(logn) 的算法通常与 O(n) 的算法组合在一起，用于实现 O(nlogn) 要求的题目。
练习
在讲解具体题目之前，我们先明确下根据时间复杂度做题的具体流程：
1. 根据数据范围选择时间复杂度
2. 根据时间复杂度选择对应的常见算法集合
3. 思考题目特征，从集合中选出合适的算法
4.根据选出的算法求解题目
例如下道题解
1248. 统计「优美子数组」
题目描述：
给你一个整数数组 nums 和一个整数 k 。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。请返回这个数组中 「优美子数组」 的数目。
示例 1：
示例 2：
示例 3：
数据范围：
解决过程：
本题的数据范围到达了 50000 ，因此我们将时间复杂度划定在 O(n) 的范围内。
根据上述「常见算法 & 时间复杂度」图，我们可以划定本题的算法集合。由于此题明显是数组上操作的问题，因此我们仅列出 O(n) 范围内关于数组的算法。
仔细观察题干，可以发现本题有两大关键特征：
1. 连续子数组
2.子数组内恰好有 k 个奇数数字
如果对「前缀和」算法有所掌握的话，凭借这两大特征不难确定此题可以用「前缀和」求解。
令 sum[i] 表示数组第 0 个数到第 i 个数中奇数的个数，因此区间 [l, r] 符合题意，当且仅当下式成立：
sum[r]−sum[l−1]=k
由此我们可以令 mp[x] 表示有多少个节点 i 满足 sum[i] = x。然后从左向右枚举，当求得第 i 个点的 sum 值后，更新 mp[sum[i]] 数组，并计算有多少个 l 满足区间 [l, i] 符合题意。累加答案即可得到最终结果，具体实现可参看下述代码。
C++ 代码实现
例题 2：
面试题 08.11. 硬币
题目描述
硬币。给定数量不限的硬币，币值为 25 分、10 分、5 分和 1 分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上 1000000007 )。
示例 1
示例 2
数据范围：
解决过程
本题的数据范围到达了 1000000 ，因此我们将时间复杂度划定在 O(n) 的范围内。再仔细观察一下「常见算法 & 时间复杂度」图，可以发现由于只有 4 种面值的硬币，因此 O(nm) 的背包也是可行的。
根据时间复杂度与「常见算法 & 时间复杂度」图，我们可以划定本题的算法集合。由于此题明显与图论、字符串等算法无关，因此我们仅列出 O(n) 、 O(nm) 范围内有一定可能性的算法。
思考题目特征 => 从集合中选出合适算法
仔细观察此题，可以发现如下几个特征：
1. 四类硬币
2. 每类硬币数量不限
3. 求组成 n 的方案数
如果对「动态规划」有一定熟悉度的话，基本可以确定此题就是「动态规划问题」，因此本题具有很明显的「子结构」性质。
然后再根据之前确定的时间复杂度 O(n) 、 O(nm) ，以及我们选出的算法，基本可以确定该动态规划问题的状态，只有如下两种：
1. f[i] 表示用四种硬币组成 i 分的方案数，属于典型线性 DP。
2. f[i][j] 表示用前 i 种硬币组成 j 分的方案数，属于背包问题。再仔细思考两种状态的转移方程，可以发现第二种采用背包思路的 DP 状态更适合解决本题，且由于硬币个数不限，因此是经典的「完全背包」问题。所以我们可以直接列出如下的转移方程（ coin[i] 表示第 i 类硬币的面值）：
可以发现， f[i][j] 的数值主要由 f [i−1][j] 与 f[i][j−coin[j]] 得到，因此我们可以压缩掉第一维，即采用滚动数组的方法，得到如下方程：
由于「完全背包」是背包问题中的经典模型，因此更具体的细节，大家可以参考下述代码。
C++代码实现
总结最后，我们来总结一下「数据范围」=> 「最终算法」的总体过程，如下图所示。
除此之外，还需注意，从「数据范围」入手思考「最终算法」只是获取题目思路的手段之一，并且在上述流程图中，「根据题目特征，筛选算法」是最为关键的步骤，这不仅要求做题者具有「挖掘题目特征」的能力，更要求做题者对于「常见算法」要有一定的熟悉度。
也正是因为这个原因，「常见算法 & 时间复杂度」对应图是具有个人特征的。每个人由于掌握的算法不同，「常见算法 & 时间复杂度」图也各不相同，因此希望大家能够有意识地构建属于自己的「常见算法 & 时间复杂度」图，并在刷题的过程中，不断更新，不断完善。力求能够在遇到自己掌握范围内的算法题时，一举击破。如果还是没有头绪，不妨试下下面的方法：
大家在做算法题时需要循序渐进，上来如果直接就做 hard 题有些耗时间，但并不是不能做，只是性价比很低，先做熟练较低难度的题目，熟练掌握所有算法之后相当于掌握了各种工具，当算法如臂使指时，做起 hard 题来就会得心应手。
如果对 DP、DFS、BFS，二分法很熟悉，我建议可以先从简单的数据结构开始，从队列、堆，二叉树到更复杂的红黑树、线段树，尽可能都可掌握。
这里推荐一本书 《图解算法数据结构》，这本书是由力扣平台知名创作者「Krahets」倾心打造，面向算法零基础学习者，以图文并茂的方式讲解算法基础知识与求职热门算法题。学完你将会掌握：
思考时间复杂度可以减少大量试错机会。如果你想出的算法在时间复杂度上无法满足题目给出的数据规模，那就说明算法还是有问题，需要思考更好的算法。有的时候，会有些模糊，比如刚好不过，或者差一点，那说明可能需要进行优化或剪枝。
做出思考很久的题目的快感是很爽，但确也浪费时间，我们的建议是平衡好两者，思考一个小时后如果没有结果就看解答。事实上很多时候超过一个小时以后还没想出来最优解，就很难在短时间内想出来了。
总的来说，刷算法题有点像一个模拟经营游戏，要平衡好学习和做题的节奏，不能操之过急，也不能把节奏放的太慢。评论留言少 BUG ！点赞转发不脱发！
声明：本文归“力扣”版权所有，如需转载请联系。
