Leetcode 第 169 场比赛回顾

零、背景

这次比赛都是大水题，不过最后一题是搜索题，卡的是剪枝算法。
很多人找不到有效的剪枝策略，导致过不了了吧。

其实剪枝策略就两个，我选择了第一个超时，换成第二个就过了。

因此有幸进入全球前 100 名了。

下面来看看这四道大水题吧。

一、不同数字之和为零

题意：给一个数字n，求构造n个不同的数字，使得这些数字之和为0。

思路：前n-1个数字随便给一个正数（比如递增），最后一个数字补负数即可。

二、二叉树所有元素

题意：给两个二叉树，求所有元素组成的即可，按升序输出。

思路：先分别递归获取两个二叉树的值，排序即可。

三、跳一跳游戏

题意：给一个数组arr和起始位置i。
我们可以从起始位置跳到i + arr[i] 和 i - arr[i]。
问这样不断的跳下去，是否可以遇到值为0的位置。

思路：搜索即可，DFS和BFS都可以。

四、字母与数字之间的难题

题意：给一个字符串数组以及一个目标字符串。
当每个字符A-Z映射到互不相同的数字0-9后，字符串就转化为了数字。
问数组里的数字之和能否等于目标数字。

样例：给一个字符串["AA", "BB"]，目标数字"CC"。
则A=>1，B=>2，C=>3可以满足11+22=33。

思路：典型的DFS题。
但是考虑到字符串长度是10，复杂度可能高达10^10。
这样肯定会超时，所以需要剪枝。

考虑到不允许有前缀零，我便想到从高位到低位枚举，然后检查是否有前缀零。
有了直接减掉，可惜最后一组样例超时了。

已经从高位到低位枚举，顺势可以想到，预先判断当前状态是不是肯定不存在答案。
什么时候不存在答案呢？ 就是目标字符串以后不管怎么取值，肯定小于前面的数组的和。

具体来说，对于目标字符串，没有枚举的字符假设值是9；对于枚举的字符串，没有枚举的字符假设值是0。
这样目标字符串的最大值如果还小于数组的和，那就肯定没答案了。
可惜样例还是超时。

然后大部分人到这里就没办法了。

我也是冥思苦想，然后想超时的原因可能是从高位剪枝，可能满足的枚举量太多了。
如果从低位剪枝，必须严格相等，是不是满足的枚举量就少多了呢？
于是我再次修改代码，没想到测试样例瞬间就出来了。
然后我就做完题了。

由于这个做了大量的预处理，代码量比较大，就不贴出来了。
想要代码的可以后台回复weekly-contest-169获取这次比赛的源代码。

五、最后

这次比赛前三题太水了，我这蜗牛般的敲代码速度，都可以在12分钟做完，那你们应该都是10分钟内吧。

最后一题虽然在剪枝上卡题了，对于我来说却是一个机会。
以后应该再也没有机会进去全球前百名了吧。

PS：后台回复weekly-contest-169获取这次比赛四道题的源代码。

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code