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-