拼多多5.9笔试个人题解

3、给一个由大小写字母组成的字符串，每次删除一个最长的且最左侧的一个连续子串（需要由相同字母构成），求最小删除次数。模拟题，暴力模拟是O(n^2)，据说这题暴力是可以AC的。一种低复杂度解法是把连续的部分组织成链表，比如aBBa变成 (a, 1) -> (B, 2) -> (a, 1) 这样，链表的好处是可以很快地删除并且合并两个端点。现在问题就是怎么找最长的那一个部分（比如之前的例子就是(B, 2)）。可以考虑用线段树维护最大值，然后通过二分的形式把最大且最左的那一个部分给找出来。找出来之后更新链表，然后同时更新线段树。复杂度O(nlog^2n)。 4、给一个正整数组成的列表，找出一个长度不小于m的子段使得其中平均值最大。暴力据说可以骗不少分。首先区间和转前缀和，设前缀和为S[i]，那么平均值就是(S[r] - S[l]) / (r - l)。给定一个平均值k，另(S[r] - S[l]) / (r - l) >= k 则有 S[r]-kr >= S[l]-kl。这样给定k，我们可以很快地找出满足上式成立的最大区间长度 t=r-l，而t关于k是单调的。这样二分答案k，然后对于每一个k找出这个t，如果t<m说明k找大了，就二分左半区间，否则二分右半区间。由于这个找t的过程需要算一个前缀最小值并且在其中二分，复杂度就是O(nlog^2n)。

大佬牛逼，我只会做汉堡那题

我亲爱的hh，牛逼！😍😍

😭第一题汉堡题我也是贪心的解法，但是爆0了还是不知道为什么

第四题暴力过了90%

牛的