标签： todo

目标

给你一个二维整数数组 points，其中 points[i] = [xi, yi] 表示第 i 个点在笛卡尔平面上的坐标。

返回可以从 points 中任意选择四个不同点组成的梯形的数量。

梯形 是一种凸四边形，具有 至少一对 平行边。两条直线平行当且仅当它们的斜率相同。

示例 1：

输入： points = [[-3,2],[3,0],[2,3],[3,2],[2,-3]]
输出： 2
解释：
有两种不同方式选择四个点组成一个梯形：
点 [-3,2], [2,3], [3,2], [2,-3] 组成一个梯形。
点 [2,3], [3,2], [3,0], [2,-3] 组成另一个梯形。

示例 2：

输入： points = [[0,0],[1,0],[0,1],[2,1]]
输出： 1
解释：
只有一种方式可以组成一个梯形。

说明：

• 4 <= points.length <= 500
• –1000 <= xi, yi <= 1000
• 所有点两两不同。

思路

和 3623.统计梯形的数目I 类似，本题的斜率可以不是 0，需要考虑垂直于 x 轴的平行线，以及平行四边形重复统计问题。

计算两个坐标点的斜率，并根据斜率分组，再在每一组中根据截距分组。计算斜率需要除法，需要考虑精度问题。需要特殊处理垂线。对于平行四边形，有两对平行的边，在计算时会重复统计。所以还要减去平行四边形的个数，由于其两条对角线的中点是重合的，利用这一性质，按照对角线的中点分组统计。

代码

性能

目标

给你一个下标从 0 开始的字符串 s 和一个整数 k。

你需要执行以下分割操作，直到字符串 s 变为 空：

• 选择 s 的最长 前缀，该前缀最多包含 k 个 不同 字符。
• 删除 这个前缀，并将分割数量加一。如果有剩余字符，它们在 s 中保持原来的顺序。

执行操作之 前 ，你可以将 s 中 至多一处 下标的对应字符更改为另一个小写英文字母。

在最优选择情形下改变至多一处下标对应字符后，用整数表示并返回操作结束时得到的 最大 分割数量。

示例 1：

输入：s = "accca", k = 2
输出：3
解释：
最好的方式是把 s[2] 变为除了 a 和 c 之外的东西，比如 b。然后它变成了 "acbca"。
然后我们执行以下操作：
1. 最多包含 2 个不同字符的最长前缀是 "ac"，我们删除它然后 s 变为 "bca"。
2. 现在最多包含 2 个不同字符的最长前缀是 "bc"，所以我们删除它然后 s 变为 "a"。
3. 最后，我们删除 "a" 并且 s 变成空串，所以该过程结束。
进行操作时，字符串被分成 3 个部分，所以答案是 3。

示例 2：

输入：s = "aabaab", k = 3
输出：1
解释：
一开始 s 包含 2 个不同的字符，所以无论我们改变哪个， 它最多包含 3 个不同字符，因此最多包含 3 个不同字符的最长前缀始终是所有字符，因此答案是 1。

示例 3：

输入：s = "xxyz", k = 1
输出：4
解释：
最好的方式是将 s[0] 或 s[1] 变为 s 中字符以外的东西，例如将 s[0] 变为 w。
然后 s 变为 "wxyz"，包含 4 个不同的字符，所以当 k 为 1，它将分为 4 个部分。

说明：

• 1 <= s.length <= 10^4
• s 只包含小写英文字母。
• 1 <= k <= 26

思路

有一个字符串 s 和一个整数 k，允许至多将 s 中的任意一个字符替换为其它小写英文字母，然后循环执行以下操作：删除字符串 s 的 最长 前缀，要求前缀中 最多 包含 k 个不同字符。求最大的删除次数。

// todo

代码

性能

目标

你有一个电影租借公司和 n 个电影商店。你想要实现一个电影租借系统，它支持查询、预订和返还电影的操作。同时系统还能生成一份当前被借出电影的报告。

所有电影用二维整数数组 entries 表示，其中 entries[i] = [shopi, moviei, pricei] 表示商店 shopi 有一份电影 moviei 的拷贝，租借价格为 pricei 。每个商店有 至多一份 编号为 moviei 的电影拷贝。

系统需要支持以下操作：

• Search：找到拥有指定电影且 未借出 的商店中 最便宜的 5 个 。商店需要按照 价格 升序排序，如果价格相同，则 shopi 较小 的商店排在前面。如果查询结果少于 5 个商店，则将它们全部返回。如果查询结果没有任何商店，则返回空列表。
• Rent：从指定商店借出指定电影，题目保证指定电影在指定商店 未借出 。
• Drop：在指定商店返还 之前已借出 的指定电影。
• Report：返回 最便宜的 5 部已借出电影 （可能有重复的电影 ID），将结果用二维列表 res 返回，其中 res[j] = [shopj, moviej] 表示第 j 便宜的已借出电影是从商店 shopj 借出的电影 moviej 。res 中的电影需要按 价格 升序排序；如果价格相同，则 shopj 较小 的排在前面；如果仍然相同，则 moviej 较小 的排在前面。如果当前借出的电影小于 5 部，则将它们全部返回。如果当前没有借出电影，则返回一个空的列表。

请你实现 MovieRentingSystem 类：

• MovieRentingSystem(int n, int[][] entries) 将 MovieRentingSystem 对象用 n 个商店和 entries 表示的电影列表初始化。
• List<Integer> search(int movie) 如上所述，返回 未借出 指定 movie 的商店列表。
• void rent(int shop, int movie) 从指定商店 shop 借出指定电影 movie 。
• void drop(int shop, int movie) 在指定商店 shop 返还之前借出的电影 movie 。
• List<List<Integer>> report() 如上所述，返回最便宜的 已借出 电影列表。

注意：测试数据保证 rent 操作中指定商店拥有 未借出 的指定电影，且 drop 操作指定的商店 之前已借出 指定电影。

示例 1：

输入：
["MovieRentingSystem", "search", "rent", "rent", "report", "drop", "search"]
[[3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]], [1], [0, 1], [1, 2], [], [1, 2], [2]]
输出：
[null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]]

解释：
MovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]);
movieRentingSystem.search(1);  // 返回 [1, 0, 2] ，商店 1，0 和 2 有未借出的 ID 为 1 的电影。商店 1 最便宜，商店 0 和 2 价格相同，所以按商店编号排序。
movieRentingSystem.rent(0, 1); // 从商店 0 借出电影 1 。现在商店 0 未借出电影编号为 [2,3] 。
movieRentingSystem.rent(1, 2); // 从商店 1 借出电影 2 。现在商店 1 未借出的电影编号为 [1] 。
movieRentingSystem.report();   // 返回 [[0, 1], [1, 2]] 。商店 0 借出的电影 1 最便宜，然后是商店 1 借出的电影 2 。
movieRentingSystem.drop(1, 2); // 在商店 1 返还电影 2 。现在商店 1 未借出的电影编号为 [1,2] 。
movieRentingSystem.search(2);  // 返回 [0, 1] 。商店 0 和 1 有未借出的 ID 为 2 的电影。商店 0 最便宜，然后是商店 1 。

说明：

• 1 <= n <= 3 * 10^5
• 1 <= entries.length <= 10^5
• 0 <= shopi < n
• 1 <= moviei, pricei <= 10^4
• 每个商店 至多 有一份电影 moviei 的拷贝。
• search，rent，drop 和 report 的调用 总共 不超过 10^5 次。

思路

代码

性能