leetcode 第198算法比赛

零、背景

回头看看记录，上次比赛竟然是一个月前。

我有整整一个月没做比赛了。

今天尝试启动做比赛，结果发现被后浪们狂虐了。

一、换酒问题

题意：初始有 a 瓶酒，b 个空酒瓶可以换一瓶酒。
问最多可以喝多少酒？

思路：模拟即可，不管 a 多大，都是指数级下降的。

PS：酒精是一级致癌物质，建议大家尽量滴酒不沾。

二、子树中标签相同的节点数

题意：给一个有根树，每个节点有一个字母。
问每个节点为根的子树上，有多少个节点与子根的字母相同。

如上图，节点 0 的字母是 a，这个子树上有 2 个 a，所以节点 0 的答案是 2。
对于其他节点，子树上与根相同的字母都是一个，即子根自身。

思路：先使用map<int, set<int>> 建树，然后 dfs 统计当前子树的答案即可。

注意事项：只需要使用一个 map ，递归后根字母的个数减去递归前根字母的个数就是当前子树的答案。

三、最多的不重叠子字符串

题意：给一个字符串 S ，一个闭环子串 s 代表着，子串 s 中的任意一个字母 c，S 中的所有 c 都在闭环子串 s 中。
问最多可以得到几个闭环子串。
如果存在多个答案，输出闭环子串总长度最小的那组答案。

分析：闭环子串的定义比较绕，不过多读几遍还是可以理解。

理解题意后，我们可以快速计算出每个字母的左右区间来。

然后根据闭环子串的定义，推出几个性质。

1、如果两个字母的区间存在交集，则这两个字母必须属于同一个闭环子串。
2、如果一个字母 a 的区间包含另一个字母 b 区间，那么最优答案里永远不会有 a， 因为 b 比 a 更优。

根据上面两个性质，我们就可以做出这两道题了。

1、先求出每个字母的左右区间

2、维护一个单调栈，合并相邻的相交区间。
对于字母，使用并查集指向最左边的字母。

3、再次使用单调栈，删除存在子区间的区间。

4、此时单调栈里就是最有答案的区间列表，构造出答案。

四、找到最接近目标值的函数值

题意：题目给一个函数func，求最小的区间l,r使得计算出的结果与target最接近。

思路：比赛的时候看错题了，& 运算看成异或了。

赛后发现这道题出发点很好，但是有个 BUG，对于那些抱着暴力试一试想法的，都水过去了。

原来图中的函数是与操作。
与操作有一个性质：操作越多，结果越小。

这个可以使用 1 的个数来理解，起初有 k 个 1。
和一个数与操作后，要么不变，要么 1 的个数减少。
减少后，其他位置的 0 都不变，现在多了更多的 0，那结果就更小了。

这个进而可以得到一个推论：以某个位置为后缀的所有区间进行函数操作后，不同的数字只有几十个，即log(N)个。
那暴力的复杂度就是n log(n)了。

当然，看题解可以发现这道题各种解法都有。

比如模拟退火、线段树+滑动窗口、RMQ+二分、甚至随机算法都来了。

五、最后

这次比赛的题其实蛮不错的。

思考题：听说每道题都很多解法，你怎么做的？

《完》

-EOF-

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