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$。

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