树链剖分
- 树链剖分
- 长链剖分
- 重链剖分
- 实链剖分
0%
求出所有子序列的能量和
发表于
分类于
leetcode
2 <= n == nums.length <= 50-108 <= nums[i] <= 1082 <= k <= n
给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。
一个子序列的 能量 定义为子序列中 任意 两个元素的差值绝对值的 最小值 。
请你返回 nums 中长度 等于 k 的 所有 子序列的 能量和 。
由于答案可能会很大，将答案对 109 + 7 取余 后返回。
示例 1：
输入： nums = [1,2,3,4], k = 3
输出： 4
解释：
nums 中总共有 4 个长度为 3 的子序列：[1,2,3] ，[1,3,4] ，[1,2,4] 和 [2,3,4] 。能量和为
|2 - 3| + |3 - 4| + |2 - 1| + |3 - 4| = 4 。
示例 2：
输入： nums = [2,2], k = 2
输出： 0
解释：
nums 中唯一一个长度为 2 的子序列是 [2,2] 。能量和为 |2 - 2| = 0 。
示例 3：
输入： nums = [4,3,-1], k = 2
输出： 10
解释：
nums 总共有 3 个长度为 2 的子序列：[4,3] ，[4,-1] 和 [3,-1] 。能量和为 `|4 - 3| + |4 -
(-1)| + |3 - (-1)| = 10` 。
提示：
最小化曼哈顿距离
发表于
分类于
leetcode
给你一个下标从 0 开始的数组 points ，它表示二维平面上一些点的整数坐标，其中 points[i] = [xi, yi] 。
两点之间的距离定义为它们的曼哈顿距离。
请你恰好移除一个点，返回移除后任意两点之间的 最大 距离可能的 最小 值。
示例 1：
**输入：** points = [[3,10],[5,15],[10,2],[4,4]]**输出：** 12**解释：** 移除每个点后的最大距离如下所示：- 移除第 0 个点后，最大距离在点 (5, 15) 和 (10, 2) 之间，为 |5 - 10| + |15 - 2| = 18 。- 移除第 1 个点后，最大距离在点 (3, 10) 和 (10, 2) 之间，为 |3 - 10| + |10 - 2| = 15 。- 移除第 2 个点后，最大距离在点 (5, 15) 和 (4, 4) 之间，为 |5 - 4| + |15 - 4| = 12 。- 移除第 3 个点后，最大距离在点 (5, 15) 和 (10, 2) 之间的，为 |5 - 10| + |15 - 2| = 18 。在恰好移除一个点后，任意两点之间的最大距离可能的最小值是 12 。示例 2：
**输入：** points = [[1,1],[1,1],[1,1]]**输出：** 0**解释：** 移除任一点后，任意两点之间的最大距离都是 0 。提示：
3 <= points.length <= 105points[i].length == 21 <= points[i][0], points[i][1] <= 108