【算法】Leetcode 第127场比赛回顾

一、背景

之前已经写了几场比赛记录了，如《Leetcode 第126场比赛回顾》和《Leecode 第88场比赛回顾》，今早一大早起来报名并参与了上午的第127场比赛，现在记录一下题解吧。

二、K 次取反后最大化的数组和

题意：给一个数组，我们有K次机会挑选一个数字来进行符号旋转，求最终的最大和。

这道题很简单，既然求和最大，那我们肯定优先把绝对值最大的负数反转了。
如果没有负数，则不断的反转最小的那个数即可。

三、笨阶乘

题意：对于阶乘factorial(n)代表n * (n-1) * (n-2) * ... 1。
对于阶乘只有一个运算符号*。
对阶乘进行一下变种，使用加减乘除四个运算符定义clumsy(n)代表n * (n-1) / (n-2) + (n-3) - (n-4) * (n-5) / (n-6) + (n-7)...。
四个运算符的优先级和数学运算一致，乘除大于加减，乘除一个级别，加减一个级别。
在除法运算中，结果需要向下取整，例如10 * 9 / 8 = 11。
告诉你一个n，求clumsy(n)的结果。

这道题经过简单的观察，可以发现公式里的数字根据优先级结合之后，分为几部分。
第一部分是n * (n-1) / (n-2)。
第二部分是+ (n-3)。
第三部分是- (n-4) * (n-5) / (n-6)。
后面的都是第二部分和第三部分的依次重复。

既然这样，我们就可以特殊处理第一部分，循环处理后两部分即可。
当然，对于开始和结尾，会有一些边界情况需要考虑。
对于开始，n不足第一部分时，直接返回答案。
对于结尾，n不够第三部分了，有多少计算多少。
具体的可以看代码，还算简单。

四、最少旋转次数

题意说的是给两个数组，相同位置可以交换，判断能否通过若干次交换，使的某一个数组的数字都相同。

这道题难度标的是中级，感觉有点夸大了。
既然相同位置交换后某一个数组的数字都相同，那两个数组第一个位置的两个值中，必有一个是这个数字。
我们分别判断即可找到这个数字，然后再判断移动到哪个数组次数最少，即可得到答案。

五、先序遍历构造二叉树

这道题看名字就大概知道了，给一个先序二叉搜索树对应的数组，求输出对应的二叉搜索树。

这道题我做了好久，不是题有多难，而是我之前精心打造的leetcode模板还不支持树。
所以我用了好长时间来调整我的模板，最终还是调出来了。
扯远了，回来看这道题。

对于二叉搜索树，有一个特征就是父节点的值大于左子树所有节点的值，小于右子树任何一个节点的值。
有了这个特征，我们就可以依靠父节点来找出左子树和右子树的范围，从而递归的构造出这颗树来。

六、最后

之前提到过，我自己精心打造了一个 LeetCode 专用的模板。
这次做了树相关的题后，发现我的模板还没覆盖到树，这次便支持了树的测试功能。
想要我的这个模板的朋友，可以在公众号后台回复leetcode获取源代码。

这次主要新增了这样几个功能：
1.LeetCode 数组形式的输出样例转化为树
2.友好的打印树
3.自动对比树的答案是否正确

-EOF-