* @lc app=leetcode.cn id=215 lang=golang * * [215] 数组中的第K个最大元素 * * https://leetcode.cn/problems/kth-largest-element-in-an-array/description/ * * algorithms * Medium (62.43%) * Likes: 2361 * Dislikes: 0 * Total Accepted: 960.1K * Total Submissions: 1.5M * Testcase Example: '[3,2,1,5,6,4]\n2' * * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。 * * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 * * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 * * * * 示例 1: * * * 输入: [3,2,1,5,6,4], k = 2 * 输出: 5 * * * 示例 2: * * * 输入: [3,2,3,1,2,4,5,5,6], k = 4 * 输出: 4 * * * * 提示： * * * 1 <= k <= nums.length <= 10^5 * -10^4 <= nums[i] <= 10^4 * * */.

* @lc app=leetcode.cn id=2336 lang=golang * * [2336] 无限集中的最小数字 * * https://leetcode.cn/problems/smallest-number-in-infinite-set/description/ * - algorithms - Medium (72.79%) - Likes: 70 - Dislikes: 0 - Total Accepted: 31.8K - Total Submissions: 43.7K - Testcase Example: '["SmallestInfiniteSet","addBack","popSmallest","popSmallest","popSmallest","addBack","popSmallest","popSmallest","popSmallest"]\n' + '[[],[2],[],[],[],[1],[],[],[]]' * * 现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。 * * 实现 SmallestInfiniteSet 类： * * * SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。 * int popSmallest() 移除 并返回该无限集中的最小整数。 * void addBack(int num) 如果正整数 num 不 存在于无限集中，则将一个 num 添加 到该无限集最后。 * * * * * 示例： * * * 输入 * ["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", * "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"] * [[], [2], [], [], [], [1], [], [], []] * 输出 * [null, null, 1, 2, 3, null, 1, 4, 5] * * 解释 * SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet(); * smallestInfiniteSet.addBack(2); // 2 已经在集合中，所以不做任何变更。 * smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 是最小的整数，并将其从集合中移除。 * smallestInfiniteSet.popSmallest(); // 返回 2 ，并将其从集合中移除。 * smallestInfiniteSet.popSmallest(); // 返回 3 ，并将其从集合中移除。 * smallestInfiniteSet.addBack(1); // 将 1 添加到该集合中。 * smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 在上一步中被添加到集合中， * ⁠ // 且 1 是最小的整数，并将其从集合中移除。 * smallestInfiniteSet.popSmallest(); // 返回 4 ，并将其从集合中移除。 * smallestInfiniteSet.popSmallest(); // 返回 5 ，并将其从集合中移除。 * * * * 提示： * * * 1 <= num <= 1000 * 最多调用 popSmallest 和 addBack 方法 共计 1000 次 * * */.

* @lc app=leetcode.cn id=2462 lang=golang * * [2462] 雇佣 K 位工人的总代价 * * https://leetcode.cn/problems/total-cost-to-hire-k-workers/description/ * * algorithms * Medium (39.03%) * Likes: 54 * Dislikes: 0 * Total Accepted: 9.7K * Total Submissions: 24.9K * Testcase Example: '[17,12,10,2,7,2,11,20,8]\n3\n4' * * 给你一个下标从 0 开始的整数数组 costs ，其中 costs[i] 是雇佣第 i 位工人的代价。 * * 同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 位工人： * * * 总共进行 k 轮雇佣，且每一轮恰好雇佣一位工人。 * 在每一轮雇佣中，从最前面 candidates 和最后面 candidates * 人中选出代价最小的一位工人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。 * * 比方说，costs = [3,2,7,7,1,2] 且 candidates = 2 ，第一轮雇佣中，我们选择第 4 位工人，因为他的代价最小 * [3,2,7,7,1,2] 。 * 第二轮雇佣，我们选择第 1 位工人，因为他们的代价与第 4 位工人一样都是最小代价，而且下标更小，[3,2,7,7,2] * 。注意每一轮雇佣后，剩余工人的下标可能会发生变化。 * * * 如果剩余员工数目不足 candidates 人，那么下一轮雇佣他们中代价最小的一人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。 * 一位工人只能被选择一次。 * * * 返回雇佣恰好 k 位工人的总代价。 * * * * 示例 1： * * 输入：costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4 * 输出：11 * 解释：我们总共雇佣 3 位工人。总代价一开始为 0 。 * - 第一轮雇佣，我们从 [17,12,10,2,7,2,11,20,8] 中选择。最小代价是 2 ，有两位工人，我们选择下标更小的一位工人，即第 3 * 位工人。总代价是 0 + 2 = 2 。 * - 第二轮雇佣，我们从 [17,12,10,7,2,11,20,8] 中选择。最小代价是 2 ，下标为 4 ，总代价是 2 + 2 = 4 。 * - 第三轮雇佣，我们从 [17,12,10,7,11,20,8] 中选择，最小代价是 7 ，下标为 3 ，总代价是 4 + 7 = 11 。注意下标为 * 3 的工人同时在最前面和最后面 4 位工人中。 * 总雇佣代价是 11 。 * * * 示例 2： * * 输入：costs = [1,2,4,1], k = 3, candidates = 3 * 输出：4 * 解释：我们总共雇佣 3 位工人。总代价一开始为 0 。 * - 第一轮雇佣，我们从 [1,2,4,1] 中选择。最小代价为 1 ，有两位工人，我们选择下标更小的一位工人，即第 0 位工人，总代价是 0 + 1 = * 1 。注意，下标为 1 和 2 的工人同时在最前面和最后面 3 位工人中。 * - 第二轮雇佣，我们从 [2,4,1] 中选择。最小代价为 1 ，下标为 2 ，总代价是 1 + 1 = 2 。 * - 第三轮雇佣，少于 3 位工人，我们从剩余工人 [2,4] 中选择。最小代价是 2 ，下标为 0 。总代价为 2 + 2 = 4 。 * 总雇佣代价是 4 。 * * * * * 提示： * * * 1 <= costs.length <= 10^5 * 1 <= costs[i] <= 10^5 * 1 <= k, candidates <= costs.length * * */.

* @lc app=leetcode.cn id=2542 lang=golang * * [2542] 最大子序列的分数 * * https://leetcode.cn/problems/maximum-subsequence-score/description/ * * algorithms * Medium (51.58%) * Likes: 73 * Dislikes: 0 * Total Accepted: 6.2K * Total Submissions: 12K * Testcase Example: '[1,3,3,2]\n[2,1,3,4]\n3' * * 给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都是 n ，再给你一个正整数 k 。你必须从 nums1 中选一个长度为 k * 的 子序列 对应的下标。 * * 对于选择的下标 i0 ，i1 ，...， ik - 1 ，你的 分数 定义如下： * * * nums1 中下标对应元素求和，乘以 nums2 中下标对应元素的 最小值 。 * 用公式表示： (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , * nums2[i1], ..

* @lc app=leetcode.cn id=789 lang=golang * * [789] 逃脱阻碍者 * * https://leetcode.cn/problems/escape-the-ghosts/description/ * * algorithms * Medium (68.50%) * Likes: 115 * Dislikes: 0 * Total Accepted: 23.9K * Total Submissions: 34.8K * Testcase Example: '[[1,0],[0,3]]\n[0,1]' * * 你在进行一个简化版的吃豆人游戏。你从 [0, 0] 点开始出发，你的目的地是 target = [xtarget, ytarget] * 。地图上有一些阻碍者，以数组 ghosts 给出，第 i 个阻碍者从 ghosts[i] = [xi, yi] 出发。所有输入均为 整数坐标 。 * * 每一回合，你和阻碍者们可以同时向东，西，南，北四个方向移动，每次可以移动到距离原位置 1 个单位 的新位置。当然，也可以选择 不动 。所有动作 同时 * 发生。 * * 如果你可以在任何阻碍者抓住你 之前 到达目的地（阻碍者可以采取任意行动方式），则被视为逃脱成功。如果你和阻碍者 同时 到达了一个位置（包括目的地） * 都不算 是逃脱成功。 * * 如果不管阻碍者怎么移动都可以成功逃脱时，输出 true ；否则，输出 false 。 * * * 示例 1： * * * 输入：ghosts = [[1,0],[0,3]], target = [0,1] * 输出：true * 解释：你可以直接一步到达目的地 (0,1) ，在 (1, 0) 或者 (0, 3) 位置的阻碍者都不可能抓住你。 * * * 示例 2： * * * 输入：ghosts = [[1,0]], target = [2,0] * 输出：false * 解释：你需要走到位于 (2, 0) 的目的地，但是在 (1, 0) 的阻碍者位于你和目的地之间。 * * * 示例 3： * * * 输入：ghosts = [[2,0]], target = [1,0] * 输出：false * 解释：阻碍者可以和你同时达到目的地。 * * * * * 提示： * * * 1 <= ghosts.length <= 100 * ghosts[i].length == 2 * -10^4 <= xi, yi <= 10^4 * 同一位置可能有 多个阻碍者 。 * target.length == 2 * -10^4 <= xtarget, ytarget <= 10^4 * * */.