讨论/题目交流/🏆2019 力扣杯 - 全国秋季编程大赛/
🏆2019 力扣杯 - 全国秋季编程大赛

image.png

你来写我来送: 欢迎大家在本条讨论下分享和编写本次 🏆 力扣杯大赛的解题思路 / 题解

在「圈子」内撰写题解文章的同学也可以将文章链接贴在本条讨论下,力扣君将在 2019 年 10 月 10 日下午 16:00 精选 两篇优质内容,分别送出 1 本 《程序员面试金典》。
1821567415874_.pic_hd.jpg

展开讨论
力扣 (LeetCode)发起于 2019-09-24
最近编辑于 2020-07-01

Problem 1
签到题,一个一个挨个比较就行。
时间复杂度 O(n)O(n)
空间复杂度 O(n)O(n)

Problem 2
还是签到,但是记住要将每一个分子分母取反并用 gcd 化简,好在最后全是正数省略了许多判断。
时间复杂度 O(n log(max(n))O(n\ log(max(n))
空间复杂度 O(1)O(1)

Problem 3
这个题直接模拟的话会不知道什么时候停止。而因为每次循环都会使得机器人向右和向上移动同样的格子数。经过若干次循环后,我们可以将新的起点当做原点,所有障碍物向左向下平移即可形成和初始状态相同(相似)的状态。
因此在开始的时候就可以判断机器人经过平移后每个障碍物是否会在机器人的路线上。只需要模拟一次就可以。
时间复杂度 O(∣command∣2)O(|command| ^ 2)
空间复杂度 O(∣command∣2)O(|command| ^ 2)

Problem 4
这个是典型的轮廓线动态规划题目。每次放置考虑从上到下,从左至右放置。按照这种规律放的话,每次放置,只需要记录从上一行的该格子到该格子前一个的状态。使用状态压缩转为 2 进制即可很方便使用 dp 进行转移。

But... 如果说记录全盘的状态,则状态数会高达 O(2mn)O(2^{mn}),在这道题的范围下,状态数堪比棋盘上的麦粒那么多。显然,需要一定技巧来减少需要记录的状态量。

dp_graph.jpg

具体说一下,就是这个题目,当我们放置每个方块的时候,只有 3 种,不放,横放和竖放。如图所示,当我们考虑在绿色格子 K0 放置的时候,能否放骨牌和灰色格子无关而只与五个红色格子的状态有关(注 1)(即如果 K5 号格没有骨牌才能竖放,K1 号格没有才能横放)。也就是说,K0 处能否放骨牌,会涉及到至多前 m 个格子的状态,因此用一个 m 维向量来表示即可(转换为 2 进制就可以作为数组下标)。当状态为 (K5, K4, K3, K2, K1) 会转移到一个新的状态 (K4, K3, K2, K1, K0)。根据具体的数值即可推算出结果。

P.S.

  1. 注意因为动态规划的顺序,横放只可以向左放,竖放只能向上放。

时间复杂度 O(m∗n∗2m)O(m * n * 2 ^ m)
空间复杂度使用普通数组则为 O(m∗n∗2m)O(m * n * 2 ^ m)
滚动数组则为 O(2m)O(2 ^ m)。

Problem 5
感觉这个题比第四题还要简单一些。
这道题是在树上操作,而每一次操作都只涉及单点和子树问题。
我们知道,处理子树问题如果能把树化为一维数组来做就可以了。而很明显这道题使用 DFS 序列这种做法,先做一次 DFS,将每个点入栈和出栈的 timestamp 记录下来,这个 timestamp 之间就是以该点为根的子树。将 DFS 序列作为新的序列,使用线段树就可以了。
时间复杂度 O(n log n+q log n)O(n\ log\ n + q\ log\ n)
空间复杂度 O(n log n)O(n\ log\ n)

25
展开全部 23 讨论