Leetcode第150场周赛

  • 时间：2019/8/18
  • 竞赛地址: https://leetcode-cn.com/contest/weekly-contest-150
  • 解决题目：4/4
  • 耗时: 1:05:04
  • 排名: 54/1472
  • 第一题，直接模拟。第二题，DFS遍历树，开一个数组，记录每一层的和。第三题，直接遍历，然后DFS计算和当前点满足条件的最小距离。第四题，观察一下肯定目标串是从出现过字符中的字典序最大的字符开始的串，维护一个R[i]代表向右延伸的和s[i]相同的最大距离。然后枚举最大字符出现的位置，对于每个位置根据R[i]去判断是否当前字符串是字典序最大的。如果两个子串R[i]最大，就判断从当前位置开始向后第一个字符不同的位置的字典序大小即可。这里可以再维护一个R2数组，也可以直接暴力，数据应该是没法卡过去的。
  • 我的代码地址：竞赛页面搜bbuf

Leetcode第7周双周赛

  • 时间: 2019/8/24
  • 解决题目: 3/4
  • 耗时: 1:30:00
  • 排名: 52/561
  • 第一题，直接模拟。第二题，STL应用。第三题，Huffleman树。第4题，一直以为是最小生成树，写了一次Kruskal，发现应该是个深林，这咋办啊，强行DFS了2次，RE了，然后似乎没了？赛后看第一名代码，建立个虚点，然后直接一发Kruskal就好了。为什么最近写个题会手抖？
  • 代码: 竞赛页面搜bbuf

Leetcode第151场周赛

  • 时间：2019/8/25
  • 解决题目: 3/4
  • 耗时: 1:09:00
  • 排名: 55/1340
    -第一题for循环判断，输入比较恶心，写了26分钟，还错了一次。第二题，直接模拟，比第一题简单。第三题，直接模拟，不过不熟悉链表的相关题目，写了很久，链表一直插入本地RE，最后1小时09分改对。第四题，就是vector模拟数据结构，由于前期耗时太多，我没写完。
  • 我的代码地址：竞赛页面搜bbuf

Leetcode第152场周赛

  • 时间 2019/8/25
  • 解决题目: 2/4
  • 耗时: 1:30:00
  • 排名: 140/1364
  • 第一题，简单组合数问题，但因为中间爆int的一个问题查了10分钟，脑子已经越来越不清醒了。第二题，模拟题。第3题，只想到一个二分*O(26)复杂度的做法，后面结束后才想到可以用一个O(26)的整体前缀和去掉这个log，果然脑子不知道去哪了。最后一题，因为一直卡在第三题，没去看，是一个子集枚举的问题，复杂度O(3^26)，这场彻底GG，下周打回来。

Leetcode第8场双周赛

  • 时间 2019/9/7
  • 解决题目: 3/4
  • 耗时: 1:00:00
  • 排名: 87/630
  • 第一题，暴力模拟。第二题，实际上很简单，但是中途不小心多写了一行bug代码，错了5发才过，罚时爆炸。第3题，二分的简单题，但忽略了lower_bound没有查找到的时候会返回长度，RE了一次。最后一题，猜了一发这个构造是唯一的，然后用BFS来做，用二维前缀和来check，WA到结束，实际上最后是个假算法，这道题技巧性非常强，看到第一名的代码我哭了，这是一道智商题，不说了，争取明天可以打回来一点。

Leetcode第153场周赛

  • 时间 2019/9/8
  • 解决题目: 3/4
  • 耗时: 1:00:00
  • 排名: 84/1432
  • 第一题，暴力模拟，没注意下标的大小关系WA了一次。第二题，蔡勒公式带进去计算就行了。第三题，脑子有点糊，开始想歪了一直以为和最大子列和的那个区间相关，发现代码难写之后想到只需要正向和反向做一次DP，然后枚举一下每个点取个最大值即可，看错了数组长度的范围，RE了一发。第4题，想错了，实际上是个DP。

第9场双周赛和154场周赛

因为本人上周出了点事，所以这两场比赛就无奈的没打。

力扣2019秋季编程大赛

  • 时间 2019/9/8
  • 解决题目4/5
  • 耗时: 1:30:00，一共是2小时的比赛
  • 排名: 83/1541
  • 题解：
    这次的题还是比较传统。首先简单说一下思路吧。
    Problem 1
    签到题， 一个一个挨个比较就行。
    时间复杂度O(n), 空间复杂度O(n).

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

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

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

Problem 5
感觉这个题比第四题还要简单一些。
这道题是在树上操作， 而每一次操作都只涉及单点和子树问题。 我们知道， 处理子树问题如果能把树化为一维数组来做就可以了。而很明显这道题使用DFS序列这种做法，先做一次DFS， 将每个点入栈和出栈的timestamp记录下来， 这个timestamp之间就是以该点为根的子树。将DFS序列作为新的序列，使用线段树就可以了。
时间复杂度 O(nlogn + qlogn), 空间复杂度 O(nlogn).
转载自Leetcode
作者：haozheyan97
链接：https://leetcode-cn.com/circle/discuss/1I3IVg/view/WSfk3R/

第5题我不小心打错了一个细节，然后WA到结束，哭爆。奖品就这样没了。

第156场周赛

  • 时间： 2019/9/29
  • 解决题目: 3/4
  • 耗时： 00:53:00
  • 排名：110/1432
  • 第一题，简单stl的应用。第二题，二分答案。第三题，卡了好久，后来发现直接暴力都可以通过这道题，因为均摊复杂度肯定达不到1e9，后来发现还可以直接用栈来做，复杂度为O(n)。最后一题，我还剩半小时，确实这题很简单，就是最常见的BFS。只需要将标记数组改为标记四个坐标即可，不过这样内存放不下，所以打算编号放到map里面标记。后面写完测试发现sample过不了，然后手上PC没配置gdb，没办法debug，只能绝望的printf，在痛苦中打出gg。

第10场双周赛

  • 时间: 2019/10/5
  • 解决题目: 4/4
  • 耗时: 1:07:13
  • 排名: 70/732
  • 第一题，暴力。第二题，暴力。第三题，BFS，但要注意中间计算会爆int，需要使用long long存储，第4题，求出原串和原串的转置串的LCS，串的总长减去LCS长度就是最少需要删除的字符数，然后和k比较即可，这题用编辑距离方式的DP也是可行的。