LeetCode Weekly 199 题解

正文索引 [隐藏]

5472. 重新排列字符串

题目链接:https://leetcode-cn.com/contest/weekly-contest-199/problems/shuffle-string/

题目大意

给定一个字符串 s 和字符串的位置数组 p,你要把字符串的每一个字符 s_i 放到 p_i 位置上。

题解

直接模拟即可,申请一个长度与 s 相同的字符串 T,然后将 s_i 填充到 T[p_i] 位置。

5473. 灯泡开关 IV

题目链接:https://leetcode-cn.com/contest/weekly-contest-199/problems/bulb-switcher-iv/

题目大意

给你一个长度为 n 的全 0 数组,现在你每一次操作可以从任意位置开始到数组结尾的数字全部反转(0->1, 1->0)。问你最少反转多少次可以的到目标数组 target。

题解

经过一番分析可以发现,我们按照顺序从前向后进行操作即可。假设当前数组为 arr, 目标数组为 target,即从小到大枚举位置 i,如果 arr\left[i\right] \neq target\left[i\right],则反转当前数组的位置i到最后的所有元素。

暴力的复杂度为 O(n^2),因为我们每一次翻转都需要模拟这个过程将 arr 从当前位置到最后的数字翻转。再次观察可以发现,如果当前枚举的是位置 i,那么其实 arr\left[i…n\right] 的数值都是相同的,因为每次修改都是改到最后,所以只需要使用一个变量记录 arr 尾部数组的值即可,复杂度优化为 O(n)

5474. 好叶子节点对的数量

题目链接:https://leetcode-cn.com/contest/weekly-contest-199/problems/number-of-good-leaf-nodes-pairs/

题目大意

给定一棵树,距离不超过 D 的叶子节点对的数量

题解

十分套路,其实就是树上统计一下然后合并答案。

cnt\left[x\right]\left[d\right] 表示 x 为根的子树内到节点 x 距离为 d 的叶子节点个数。

假设 l, r 分别是 x 的左右孩子。
如果左右孩子都存在,那么 l, r 子树内的叶子节点经过通过节点 x 联通,我们只需要统计距离不超过 D 的即可,这是一个乘法原理:

ans +=\sum_{d=1}^D \sum_{i=0}^{d-2} cnt[l][i] \cdot cnt[r][d-2-i]

然后我们只需要从左右孩子l, r的 cnt 更新得到x的 cnt即可。

5462. 压缩字符串 II

题目链接:https://leetcode-cn.com/contest/weekly-contest-199/problems/string-compression-ii/

题目大意

给定一个字符串 S,我们可以将其删除不超过 K 个字符,问最短的行程长度编码是多少。

题解

首先我们可以发现这个问题可以从前向后做,假设我们已经知道了前面一段的答案,其后删掉一些字符,再接上一段,那么我们只需要知道前面一段结尾是什么字符,连续了多少个即可。由此,我们就知道了如何做,以及状态表示。

dp\left[i\right]\left[len\right]\left[k\right] 表示以字符串 S\left[1…i\right]内删除 k 个字符(保证最后一个第 i 个没有被删掉),最后一个字符持续 len 个的最短行程距离。

那么转移的时候,我们枚举一个位置 i 和一个处理过的位置 j, j<i 及其状态 dp\left[j\right]\left[len\right]\left[k\right],我们尝试从此状态转移到位置 i
此转移要删除 S\left[j+1…i-1 \right] 的共 i-j-1 个字符。
如果 S\left[j\right]\neq S\left[i\right],不会出现编码合并,直接尝试转移 dp\left[i\right]\left[1\right]\left[k + (i-j-1)\right]\leftarrow dp\left[j\right]\left[len\right]\left[k\right] + 1
如果 S\left[j\right] = S\left[i\right],会出现编码合并。我们需要重新计算一下编码长度的差值,再更新: dp\left[i\right]\left[len+1\right]\left[k + (i-j-1)\right]\leftarrow dp\left[j\right]\left[len\right]\left[k\right] + deltaLen

答案就是所有的符合要求状态中长度最少的,见代码。