lucifer

聊聊刷题中的**顿悟**时刻

  |  

和几位一直坚持刷题好朋友讨论了一下刷题的顿悟时刻,他们几位大都取得了不错的 offer,比如 Google 微软,Amazon,BAT 等。

通过和他们的沟通,我发现了大家顿悟时刻都是类似的。那具体他们有哪些相似点呢?我们一起来看下。

1. 同样的类型要刷很多才能顿悟

比如你想顿悟二分,那么首先你需要做足够多的二分题。

而由于二分其实是一个大的分类。因此理论上你如果想对二分大类顿悟,那么必不可少的是先做足够多的二分题,并且这些题目可以覆盖所有的二分类型

比如西法总结的基础二分,最左最右二分以及能力检测二分,其中大部分有点困难的题目都是能力检测二分。

对二分不熟悉的可以看下西法之前总结的《二分专题》:

那么推而广之,如果你想对刷算法题整体进行顿悟,那么就不得不先做足够多的题目,且这些题目能覆盖所有你想顿悟的考点

这也就是说为什么你看的大佬中的大佬都刷了上千道题的原因。因为没有上千道题目的积累,你很难对所有题目类型都顿悟的。当然你如果只是应付大多数的考点并且不参与竞赛的话,也许小几百道也是 ok 的。

2. 回顾做过的题目

有的同学比较直接,他们就是直接复习做过的题目。而有的同学则是通过做新的题目回想到之前做过的某些题,从而达到复习的作用。

不管是哪种类型。他们都必须经过一个阶段,那就是和已经做过的题目建立联系。如果你只是盲目做题的话,效率肯定上不去。

最开始刷题的时候,我会建立一些 anki 卡片。这其实就是为了强制回顾做过的题目。另外做新的题目的时候,我会强迫自己思考:

  • 这道题考察了什么知识?
  • 和之前做过的哪些题可以建立联系?
  • 是否可以用之前刷题的解法套?
  • corner case 有哪些?
  • 。。。

经过这些思考,慢慢就会把做过的题目有机地结合起来,而不是让这些题目变成彼此的信息孤岛。

3. 对做过的题目进行抽象

这个是我要讲的最后一点,但是这点却尤为重要,说它是最重要也不过分。

一方面,如果一道题目没有经过抽象,那么我们很难记住,很难在未来回忆起来。另一方面,如果一道题目能够抽象为纯粹的题目,那么说明你对这个题目看的比较透彻了。将来碰到换皮题,你一抽象,就会发现: 这不就是之前 xxxx 的换皮题么?

经常看我题解和文章的同学知道我之前写过不少换皮题的扒皮解析,这就是我做题和写文章风格。

在这里,我再举个例子。

注意:下面举的三道题例子都需要你掌握二分法的能力检测二分,如果不了解建议先看下我上面的文章。

Shopee 的零食柜

这是 shopee 的校招编程题。

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
shopee的零食柜,有着各式各样的零食,但是因为贪吃,小虾同学体重日益增加,终于被人叫为小胖了,他终于下定决心减肥了,他决定每天晚上去操场跑两圈,但是跑步太累人了,他想转移注意力,忘记痛苦,正在听着音乐的他,突然有个想法,他想跟着音乐的节奏来跑步,音乐有7种音符,对应的是1到7,那么他对应的步长就可以是1-7分米,这样的话他就可以转移注意力了,但是他想保持自己跑步的速度,在规定时间m分钟跑完。为了避免被累死,他需要规划他每分钟需要跑过的音符,这些音符的步长总和要尽量小。下面是小虾同学听的歌曲的音符,以及规定的时间,你能告诉他每分钟他应该跑多少步长?



输入描述:
输入的第一行输入 n(1 ≤ n ≤ 1000000,表示音符数),m(1<=m< 1000000, m <= n)组成,

第二行有 n 个数,表示每个音符(1<= f <= 7)


输出描述:
输出每分钟应该跑的步长
示例1
输入
8 5 6 5 6 7 6 6 3 1
输出
11

链接:https://www.nowcoder.com/questionTerminal/24a1bb82b3784f86babec24e4a5c93e0?answerType=1&f=discussion
来源:牛客网

思路

经过抽象,这道题本质上就是给你一个数组(数组值范围是 1 到 7 的整数),让你将数组分为最多 m 子数组,求 m 个子数组和的最小值

直接回答子数组和最小值比较困难,但是回答某一个具体的值是否可以达到相对容易。

比如回答子数组和最小值为 100 可以不可以相对容易。因为我们只需要遍历一次数组,如果连续子数组大于 100 就切分新的一块,这样最后切分的块数小于等于 m 就意味着 100 可以。

另外一个关键点是这种检测具有单调性。比如 100 可以,那么任何大于 100 的数(比如 101)肯定都是可以的。如果你看过我上面的《二分专题》或者做过不少能力检测二分的话, 不难想到可以利用这种单调性做能力检测二分得到答案。并且我们要找到满足条件的最小的数,因此可以套用最左能力检测二分得到答案。

代码

暂时不写,因为这道题和后面的一道题是一样的。

410. 分割数组的最大值

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
给定一个非负整数数组 nums 和一个整数 m ,你需要将这个数组分成 m 个非空的连续子数组。

设计一个算法使得这 m 个子数组各自和的最大值最小。

 

示例 1:

输入:nums = [7,2,5,10,8], m = 2
输出:18
解释:
一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18,在所有情况中最小。
示例 2:

输入:nums = [1,2,3,4,5], m = 2
输出:9
示例 3:

输入:nums = [1,4,4], m = 3
输出:4
 

提示:

1 <= nums.length <= 1000
0 <= nums[i] <= 106
1 <= m <= min(50, nums.length)

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/split-array-largest-sum

思路

这道题官方难度是 hard。和前面题抽象后一模一样,不用我多解释了吧?

你看经过这样的抽象,是不是有种殊途同归的顿悟感觉?

代码

代码支持:Python3

Python3 Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
lo, hi = max(nums), sum(nums)
def test(mid):
cnt = acc = 0
for num in nums:
if acc + num > mid:
cnt += 1
acc = num
else:
acc += num
return cnt + 1 <= m

while lo <= hi:
mid = (lo + hi) // 2
if test(mid):
hi = mid - 1
else:
lo = mid + 1
return lo

你以为这就完了么? 类似的题目简直不要太多了。西法再给你举个例子。

LCP 12. 小张刷题计划

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
为了提高自己的代码能力,小张制定了 LeetCode 刷题计划,他选中了 LeetCode 题库中的 n 道题,编号从 0 到 n-1,并计划在 m 天内按照题目编号顺序刷完所有的题目(注意,小张不能用多天完成同一题)。

在小张刷题计划中,小张需要用 time[i] 的时间完成编号 i 的题目。此外,小张还可以使用场外求助功能,通过询问他的好朋友小杨题目的解法,可以省去该题的做题时间。为了防止“小张刷题计划”变成“小杨刷题计划”,小张每天最多使用一次求助。

我们定义 m 天中做题时间最多的一天耗时为 T(小杨完成的题目不计入做题总时间)。请你帮小张求出最小的 T是多少。

示例 1:

输入:time = [1,2,3,3], m = 2

输出:3

解释:第一天小张完成前三题,其中第三题找小杨帮忙;第二天完成第四题,并且找小杨帮忙。这样做题时间最多的一天花费了 3 的时间,并且这个值是最小的。

示例 2:

输入:time = [999,999,999], m = 4

输出:0

解释:在前三天中,小张每天求助小杨一次,这样他可以在三天内完成所有的题目并不花任何时间。

 

限制:

1 <= time.length <= 10^5
1 <= time[i] <= 10000
1 <= m <= 1000

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/xiao-zhang-shua-ti-ji-hua

思路

和前面的题目类似。经过抽象,这道题本质上就是给你一个数组(数组值范围是 1 到 10000 的整数),让你将数组分为最多 m 子数组,每个子数组可以删除最多一个数,求 m 个子数组和的最小值

和上面题目唯一的不同是,这道题允许我们在子数组中删除一个数。显然,我们应该贪心地删除子数组中最大的数。

因此我的思路就是能力检测部分维护子数组的最大值,并在每次遍历过程中增加判断:如果删除子数组最大值后以后可以满足子数组和小于检测值(也就是 mid)。

代码

代码支持:Python3

Python3 Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def minTime(self, time: List[int], m: int) -> int:
def can(mid):
k = 1 # 需要多少天
t = 0 # 当前块的总时间
max_time = time[0]
for a in time[1:]:
if t + min(max_time, a) > mid:
t = 0
k += 1
max_time = a
else:
t += min(max_time, a)
max_time = max(max_time, a)
return k <= m

l, r = 0, sum(time)

while l <= r:
mid = (l+r)//2
if can(mid):
r = mid - 1
else:
l = mid + 1
return l

时间复杂度的话三道题都是一样的,我们来分析一下。

我们知道,时间复杂度分析就看执行次数最多的代码即可,显然这道题就是能力检测函数中的代码。由于能力检测部分我们需要遍历一次数组,因此时间为 $O(n)$,而能力检测函数执行的次数是 $logm$。因此时间复杂度都是 $nlogm$,其中 n 为数组长度,m 为数组和。

总结

顿悟真的是一种非常美妙的感觉,我通过采访几位大佬发现大家顿悟的经历都是类似的,那就是:

  1. 同样的类型要刷很多才能顿悟
  2. 回顾做过的题目
  3. 对做过的题目进行抽象

对第三点西法通过三道题给大家做了细致的讲解,希望大家做题的时候也能掌握好节奏,举一反三。最后祝大家刷题快乐,offer 多多。


 评论


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Material X 作为主题 。
载入天数...载入时分秒...