leetcode 第 320 场算法比赛

零、背景

之前提到，我拉了一个算法群，用于分享 leetcode 每日一题的题解以及算法咨询讨论。
对算法感兴趣的朋友可以关注公众号，在对话框里回复 “算法群” 获得进群方法。

最近七天每日一题，有 4 道比较难的题，如果你都做了，那就赚大了。

2022-11-14 第 805 题，求数组分为两份均值相等，问题转化为背包问题，数据量太大，对半枚举。
2022-11-16 第 775 题，问逆序数与相邻元素逆序数是否相等。可以单独求逆序数，也可以结合起来贪心计算。
2022-11-17 第 792 题，是否是子序列。分享了四种方法，其实还有第五个方法字典树。
2022-11-18 第 891 题，求所有子序列宽度的和。比较难的题，通过公式推导，复用前缀信息得到答案。

一、数组中不等三元组的数目

题意：给一个数组，问值互不相等的三元组有多少个。

思路：数据量不大，三层循环判断即可。

二、二叉搜索树最近节点查询

题意: 给一个二叉树，问树中大于等于 x 和小于等于 x 的值分别是多少？

思路：二叉树的值存到数组中，排序，然后二分查找即可。

三、到达首都的最少油耗

题意：给一个以 0 为根的有根树，每个节点有一个人。
每辆车最多做 K 个人，可以从任意一个节点发起一辆车，开往根节点。
问所有车最少行驶多少距离，才能把所有人拉到根节点。

思路：首先需要理解题意，并不是所有车到需要开到根节点。
如果在一个子树上，部分车可以拉所有人，其余车可以不再行驶的。

这句话的含义是子树的人可以合并到一个车上，剩余的车只与人有关，与车无关。
因此只需要递归求出子树有多少人，就可以求出当前子树到父节点需要几辆车，从而求出最小行驶距离。

四、完美分割的方案数

思路：给一个数组，问是否可以将数组分隔为 k 个不重叠的子数组，每一个子数组需要满足最小长度，且首个数字是质数，最后一个数组不是质数。
求分隔方案数。

思路：典型的形态规划题。

状态定义: dp(n, k) 前 n 个数字分隔为 k 个子数组的方案数。
状态转移方程：

dp(n,k) = sum(dp(i, k-1))
val[i+1, n] 是满足要求的子数组

复杂度：O(n^3)
比赛的时候不会超时。

优化：假设 dp(aj, k-1), j=[0,m] 都有答案，val[am+1,n]也是合法子数组，则

dp(n, k) = dp(a0, k-1) + dp(a1, k-1) + ... + dp(am, k-1)

而对于 dp(am, k), 状态转移方程展开为

dp(am, k) =  dp(a0, k-1) + dp(a1, k-1) + ... + dp(am-1, k-1)

合并两个方程，可以得到下面的转移方程

dp(n, k) = dp(am, k-1) + dp(am, k)

满足这个公式的条件是 am 是非质数，am+1 是质数，这个可以预处理得到。

复杂度：O(n^2)

五、最后

这周的每一一题有四道题比较复杂，而周赛，最后一题也有点复杂。
当然，最后一题不做优化也可以通过，说明数据有点弱。
但是，我还需要掌握如何优化，从而使得算法足够满足，即使数据强了也不会超时。

加油，算法人。

《完》

-EOF-

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