Leetcode第135场比赛回顾

一、背景

上周末同样因为五一调休，我没有参加比赛。

而五一后的前几天，一方面工作上要处理的事情较多，另一方面，最近在进一步研究 protobuf 协议的源码。
之前曾写过 protobuf 的文章 《协议之Google Protocol Buffer》，里面提到过，Protocol Buffer的代码特别多， 本来一个很简单的转换功能， 实现的特别复杂。
因为这个，我再次阅读源码时还是废了不少时间来了解一些细节，然后工作上计划对 protobuf 的序列化与反序列化做一些优化，后面有时间了写篇文章分析给大家。

总之，由于一些列原因，这几天都没有写文章，今天开始应该可以继续恢复正常的节奏。

下面来看看这次比赛的四道题吧。

PS：关于《Leetcode互动编程》项目，现在流程差不过已经确定了。
有一些小伙伴也在陆续的贡献自己做的题了，欢迎大家参与这个项目。
地址：https://github.com/tiankonguse/leetcode-solutions

一、有效的回旋镖

题号：1037
题目：Valid Boomerang
题意：判断三点是否可以组成三角形。

思路：使用向量的叉乘就可以判断两个向量是否平行了。

二、求二叉搜索树的更大和树

题号：1038
题目：Binary Search Tree to Greater Sum Tree
题意：求二叉搜索树每个定点的更大和。
二哈搜索树定义：左子树所有节点小于等于根节点，右子树所有节点大于等于根节点，子树通用保持这个性质。
更大和定义：大于等于当前节点的值的和。

思路：dfs 从大到小遍历这棵树，遍历的时候顺便求和，然后计算对应节点的更大和。

三、多边形三角剖分的最低得分

题号：1039
题目：Minimum Score Triangulation of Polygon
题意：给一个凸多边形，按顶点划分为一些三角形。划分的总代价为所有三角形三边乘积的和。求总代价最小的划分。

思路：典型的动态规划题。
定义f(0,n)为0~n这些顶点组成的多边形的最优划分。
只看顶点0和顶点n组成的边，则1~n-1这些顶点都可以当做第三个顶点和这条边组成一个三角形。
假设选择的顶点是k，则此时可以将多边形分为三部分：多边形f(0,k)、三角形0,k,n、多边形f(k,n)。
在1~n-1这些划分中的最小值就是f(0,n)的最优值。

我的习惯是使用dfs来实现，也即是push down。
实际上使用递推来实现，也就是push up的话会更简单，两层循环即可。

四、移动石子直到连续 II

题号：1040
题意：Moving Stones Until Consecutive II
题意：给一些互不相同的数字，每次可以将最大的数字或者最小的数字进行修改。修改后这个值不能是最大值和最小值。
最终不能移动时，结束。求移动的最大步数和最小步数。

思路：先来看几个基本原则。
1.不能移动的条件是所有数字连续。
2.对于最小数字，移动后不是最小数字，所以一下可以跳跃最小数字和次小数字之间的空白。
3.对于最大数字是同样的道理。

接下来，来讨论最大步数和最小步数分别怎么得到。
PS：如果你没做这道题，不建议你看下面的分析了。

对于最大步数，肯定是一步步移动最优。
但是由于前面的原则2和原则3，第一次移动有可能没办法只移动一次，所以我们会选择空白最小的那个边界进行第一次移动。
第一次以后，后续肯定可以一步步的移动。
每移动一步，最大值和最小值的差就减一，直到不能移动。

对于最小步数，目的是尽可能每个数字只移动一次。

潜意思是认为可以贪心，但是情况比较多，我在做题的时候没去证明，于是使用枚举+二分的方法来做的。
最终数字的区间长度是固定的，这里枚举区间的左边界。
区间固定后，答案也是固定的，通过二分可以计算得到答案。
考虑到区间在10^9内，而数字只有10^4个，这里需要进行剪枝，快速跳过显然无关的区间。

简单分析后，可以发现，最优值区间的左边界只可能在数字的-2,+2范围内（证明略）。
所以这里枚举所有数字的-2,+2来当做左区间，从而可以在O(n log(n))内求出答案。

当然，这道题是可以贪心的。
贪心的假设是：最优答案区间肯定由原始数字里面连续数字最长区间的接触上移动得到。
既然区间确定了，那答案也就确定了，所以复杂度是O(n)。

六、最后

这次比赛涉及到几何题、动态规划、简单树、贪心。
其中前三道是常见的问题，而最后一道，则属于启发式的算法，想到了就会，想不到就不会，没有套路的。

PS：最终这些题做完后，长这个样子。现在看来清晰多了。

-EOF-