进阶分享|做算法题的特别技巧及思路
众所周知,算法题主要有两大难点。
一是「实现」,即算法本身的难度。
二是「思路」,代表你能否想到使用这个算法来解决题目。
并且对于有一定刷题基础的同学来说,力扣上大部分简单、中等题所涉及的算法都是非常常见的算法,即算法本身不存在难度,最大的难点在于「思路」,即如何想到适合本题的算法。
而解决「思路」问题,除了大量刷题积累经验之外,还可以采用一定的「巧劲」,从时间复杂度这个角度入手筛选出合适的算法。本文的主要目的就是向大家介绍这种「巧劲」是如何在具体解题过程中发挥作用的,会分成三个部分带大家介绍~(码住收藏吧)
如何确定一道题合适的时间复杂度?最简单、快捷的方式就是通过观察题目中的数据范围来确定。
不过你可能马上会反驳,力扣上并不是所有题目都有数据范围,那又该如何确定?在没有数据范围的情况下也可以采用这种方式来思考,我们会在后续「练习」部分进行详细说明。
言归正传,如何通过数据范围来确定合适的时间复杂度?
通常来说,在力扣上,Python 可以支持到 10*7 的时间复杂度;C++ 会稍微多一点,大概 10*7 - 10*8 之间。因此我们可以得到如下表所示的,数据范围与算法大致时间复杂度的对应表。
此处有两点需要注意:
1. 上图仅列出了时间复杂度较为固定的常见算法,而类似于动态规划、贪心、暴力等时间复杂度百变多样的算法并未列出。
2. O(logn) 的算法通常与 O(n) 的算法组合在一起,用于实现 O(nlogn) 要求的题目。
在讲解具体题目之前,我们先明确下根据时间复杂度做题的具体流程:
1. 根据数据范围选择时间复杂度
2. 根据时间复杂度选择对应的常见算法集合
3. 思考题目特征,从集合中选出合适的算法
例如下道题解
题目描述:
给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字,我们就认为这个子数组是「优美子数组」。请返回这个数组中 「优美子数组」 的数目。
示例 1:
输入:nums = [1,1,2,1,1], k = 3
输出:2
解释:包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2:
输入:nums = [2,4,6], k = 1
输出:0
解释:数列中不包含任何奇数,所以不存在优美子数组。
示例 3:
输入:nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出:16
数据范围:
1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length
解决过程:
数据范围 => 时间复杂度
本题的数据范围到达了 50000,因此我们将时间复杂度划定在 O(n) 的范围内。
时间复杂度 => 常见算法集合
差分、前缀和、双指针、桶排序、单调栈、单调队列
思考题目特征 => 从集合中选出合适算法
1. 连续子数组
如果对「前缀和」算法有所掌握的话,凭借这两大特征不难确定此题可以用「前缀和」求解。
C++ 代码实现
class Solution {
vector<int> mp;
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int sum = 0, ans = 0, n = nums.size();
mp.resize(n + 2, 0);
mp[0] = 1;
for(auto y:nums){
if(y % 2) sum++;
mp[sum]++;
if(sum-k >= 0) ans += mp[sum-k];
}
return ans;
}
};
例题 2:
题目描述
示例 1
输入: n = 5
输出:2
解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1
示例 2
n = 10 :
输出:4
有四种方式可以凑成总金额: :
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1
数据范围:
0 <= n (总金额) <= 1000000
解决过程
数据范围 => 时间复杂度
本题的数据范围到达了 1000000,因此我们将时间复杂度划定在 O(n) 的范围内。再仔细观察一下「常见算法 & 时间复杂度」图,可以发现由于只有 4 种面值的硬币,因此 O(nm) 的背包也是可行的。
时间复杂度 => 常见算法集合
根据时间复杂度与「常见算法 & 时间复杂度」图,我们可以划定本题的算法集合。由于此题明显与图论、字符串等算法无关,因此我们仅列出 O(n) 、 O(nm) 范围内有一定可能性的算法。
差分、前缀和、双指针、桶排序、单调栈、单调队列、背包问题
思考题目特征 => 从集合中选出合适算法
仔细观察此题,可以发现如下几个特征:
1. 四类硬币
2. 每类硬币数量不限
3. 求组成 n 的方案数
如果对「动态规划」有一定熟悉度的话,基本可以确定此题就是「动态规划问题」,因此本题具有很明显的「子结构」性质。
1. f[i] 表示用四种硬币组成 i 分的方案数,属于典型线性 DP。
f[i][j] = f[i-1][j]
f[i][j] = f[i][j] + f[i][j-coin[i]]
可以发现, f[i][j] 的数值主要由 f [i−1][j] 与 f[i][j−coin[j]] 得到,因此我们可以压缩掉第一维,即采用滚动数组的方法,得到如下方程:
f[j] = f[j] + f[j-coin[i]]
由于「完全背包」是背包问题中的经典模型,因此更具体的细节,大家可以参考下述代码。
C++代码实现
class Solution {
vector<int> f;
int coin[4] = {25, 10, 5, 1}, mod = 1e9+7;
public:
int waysToChange(int n) {
f.resize(n + 2, 0);
f[0] = 1;
for(int i = 0; i < 4; i++)
for(int j = coin[i]; j <= n; j++)
f[j] = (f[j] + f[j-coin[i]]) % mod;
return f[n];
}
};
学习一些更加复杂的算法
大家在做算法题时需要循序渐进,上来如果直接就做 hard 题有些耗时间,但并不是不能做,只是性价比很低,先做熟练较低难度的题目,熟练掌握所有算法之后相当于掌握了各种工具,当算法如臂使指时,做起 hard 题来就会得心应手。
如果对 DP、DFS、BFS,二分法很熟悉,我建议可以先从简单的数据结构开始,从队列、堆,二叉树到更复杂的红黑树、线段树,尽可能都可掌握。
这里推荐一本书 👉《图解算法数据结构》,这本书是由力扣平台知名创作者「Krahets」倾心打造,面向算法零基础学习者,以图文并茂的方式讲解算法基础知识与求职热门算法题。学完你将会掌握:
数据结构与算法的核心知识点
熟悉互联网笔面试的主要算法题型
做提前思考时间复杂度
适当的查看官方题解,不要让自己卡太久
做出思考很久的题目的快感是很爽,但确也浪费时间,我们的建议是平衡好两者,思考一个小时后如果没有结果就看解答。事实上很多时候超过一个小时以后还没想出来最优解,就很难在短时间内想出来了。
总的来说,刷算法题有点像一个模拟经营游戏,要平衡好学习和做题的节奏,不能操之过急,也不能把节奏放的太慢。评论留言少 BUG !点赞转发不脱发!
BY /
本文作者:力扣
编辑&版式:Janson
声明:本文归“力扣”版权所有,如需转载请联系。
点个在看,少个 bug
微信扫码关注该文公众号作者