网友让你建网站做商城,中国版动漫网站模板,百度云搜索引擎入口百度网盘,史丹利网站开发团队接下来会以刷常规题为主 #xff0c;周赛的难题想要独立做出来还是有一定难度的#xff0c;需要消耗大量时间
比赛地址
3011. 判断一个数组是否可以变为有序
public class Solution {public int minimumCost(int[] nums) {if (nums.length 3) {// 数组长度小于3时周赛的难题想要独立做出来还是有一定难度的需要消耗大量时间
比赛地址
3011. 判断一个数组是否可以变为有序
public class Solution {public int minimumCost(int[] nums) {if (nums.length 3) {// 数组长度小于3时无法分割成3个子数组return -1;}int minCost Integer.MAX_VALUE;int n nums.length;// 第一个分割点至少在索引1第二个分割点至少在索引2for (int i 1; i n - 1; i) {for (int j i 1; j n; j) {int cost nums[0] nums[i] nums[j];minCost Math.min(minCost, cost);}}return minCost;}
}
100164. 通过操作使数组长度最小
冒泡排序
class Solution {public boolean canSortArray(int[] nums) {int n nums.length;for (int i 0; i n - 1; i) {for (int j 0; j n - i - 1; j) {if (Integer.bitCount(nums[j]) Integer.bitCount(nums[j 1]) nums[j]nums[j 1]) {// 如果前一个元素的1的数量大于后一个元素的1的数量交换它们int temp nums[j];nums[j] nums[j 1];nums[j 1] temp;}}}// 遍历完后检查数组是否有序for (int i 0; i n - 1; i) {if (nums[i] nums[i 1]) {return false;}}return true;}
}
100181. 将数组分成最小总代价的子数组 I
当 xy 时x mod yx 因此如果选择数组中的两个不相等的元素则可以删除较大元素保留较小元素。 用 minNum表示数组 nums 中的最小元素 用 minCount 表示数组 nums 中的 minNum 的出现次数 分别考虑 minCount1 和 minCount1 的情况。 如果 minCount1 则可以每次选择 minNum 和另一个元素由于 minNum 一定小于另一个元素因此总是可以删除另一个元素保留 minNum直到数组 nums 中只有一个元素 minNum数组 nums的最小长度是 1。 如果 minCount1 如果数组 nums 中存在一个元素 num 满足 num mod minNum≠0 记 newNum (num mod minNu)则必有 0newNumminNum 可以在一次操作中选择 num 和 minNum 删除这两个元素并添加元素newNum。由于 newNum minNum 因此 newNum 成为数组 nums 中的新的最小元素且最小元素唯一之后可以每次选择 newNum 和另一个元素其效果是删除另一个元素保留 newNum 直到数组 nums 中只有一个元素 newNum 数组 nums 的最小长度是 1如果数组 nums 中不存在元素 num 满足 num mod minNum ≠ 0 则无法通过操作得到小于 minNum 的元素因此在将所有大于 minNu 的元素删除之后剩余 minCount 个元素 minNum 。由于每次可以选择 2 个元素 minNum 执行操作得到元素 0 无法继续操作因此 minCount 个元素 minNum 的最多操作次数可以根据count_min的奇偶性判断 class Solution:def minimumArrayLength(self, nums: List[int]) - int:min_val min(nums)count_min nums.count(min_val)for num in nums:if num % min_val ! 0:return 1 # 产生了新的更小值# 没有产生新的最小值计算最小值的数量return (count_min ) // 2 1 if count_min % 2 ! 0 else count_min // 2
100178. 将数组分成最小总代价的子数组 II
一、直接用滑动窗口求解
这种方法会超时
class Solution:def minimumCost(self, nums: List[int], k: int, dist: int) - int:first nums[0] # 初始元素的代价window_size dist 1 # 窗口大小minimumCost float(inf) # 初始化最小代价为无穷大# 遍历数组寻找除第一个和最后一个元素之外的最小的 k-1 个元素for start in range(1, len(nums) - window_size 1):window nums[start:start window_size]sorted_window sorted(window)# 获取除第一个的 k-1 个最小元素的和window_cost sum(sorted_window[:k-1])# 更新最小代价minimumCost min(minimumCost, window_cost)# 最终的最小总代价是第一个元素的代价加上最小窗口代价return first minimumCost
二、引入堆的代码实现
效率和之前的方法相差无几
class Solution:def minimumCost(self, nums: List[int], k: int, dist: int) - int:first nums[0]n len(nums)minimumCost float(inf)for start in range(1, n - dist):# 维护一个大小为 dist 1 的最小堆min_heap nums[start:start dist 1]heapq.heapify(min_heap)window_cost 0# 弹出最小的 k-1 个元素并计算它们的和for _ in range(k-1):if min_heap:window_cost heapq.heappop(min_heap)minimumCost min(minimumCost, window_cost)return first minimumCost
三、大小顶堆、延迟删除、滑动窗口
这道题目的思路是利用滑动窗口结合两个堆优先队列来找出序列中指定数量(k-1)的最小数的和它们是从序列的某个区间该区间长度由dist决定中选择出来的。这个序列中的第一个数 (nums[0]) 是固定的所以总是被包含在结果中。
下面是详细的解题步骤 初始化两个堆一个小顶堆 small 来保存当前窗口中的最小的 k-2 个数以及一个大顶堆 big 来保存窗口内剩余的数。 使用 HashMap 进行延迟删除为了实现有效地从堆中删除特定的非堆顶元素创建两个 HashMap (smallMark 和 bigMark) 来标记堆中元素是否已经被 删除。该删除实际上是延迟执行的即直到这个元素出现在堆顶时才真正被排除。 填充初始窗口从 nums 数组的第二个元素开始将 dist1 长度内的元素放入 big 堆。 从 big 中取出 k-2 个最小元素这 k-2 个元素是将要加入 small 的记录这 k-2 个数的和作为窗口的当前总和。 滑动窗口在数组中滑动窗口并动态维护这两个堆以保持正确的最小 k-2 个数的总和。 调整堆当窗口滑动导致元素移出窗口时更新 small 堆以保持其有效性并进行相应的调整。如果移出的元素当前在 small 中则它需要被标记为已删除如果它在 big 中则直接标记为已删除。 处理新进入窗口的元素窗口滑动时可能会有新的元素进入。这些新元素需要加入到 big 堆中。从 big 中取出的最小元素会放入 small 堆并更新当前窗口总和sum。 求解最终结果在滑动窗口过程中每次窗口更新后计算此时的窗口总和加上 nums[0]固定加入。所有窗口中总和的最小值即为所求问题的答案。
class Solution {// small是小顶堆 维护前k-2小的数// big是大顶堆 维护窗口内剩下的数PriorityQueueInteger small, big;// 标记当前元素是否已经被删除以及被删除的个数HashMapInteger, Integer smallMark, bigMark;// samll和big当前未被删除的元素个数int smallSiz, bigSiz;long sum;public long minimumCost(int[] nums, int k, int dist) {// k个 除掉第一个 还要选k-1个// 枚举第2个 nums[i] nums[i1]... nums[idist] 里选k-2个最小的数// nums[i1] nums[ik-2]small new PriorityQueue(Collections.reverseOrder());smallSiz 0;smallMark new HashMap();big new PriorityQueue();bigSiz 0;bigMark new HashMap();// 当前小顶堆的和 也就是前k-2小的和sum 0;int n nums.length;// 把nums[11]...nums[1dist]里的数加入到big里for (int i 2; i Math.min(n-1, dist1); i) {big.add(nums[i]);bigSiz;}// 取出前k-2小的数放入smallfor (int i 0; i k-2; i ) {int tmp big.poll();bigSiz--;sum tmp;small.add(tmp);smallSiz;}long res nums[0] nums[1] sum;// 枚举第二个数的位置// 枚举的位置从i-1变成i时 nums[i]离开了窗口 nums[idist]进入了窗口for (int i 2; i k-2 n; i) {// 移除nums[i]// 因为要访问small.peek() 为了确保small.peek()是未被删除的元素 需要先更新smallupdateSmallPeek();// nums[i]在前k-2小里if (smallSiz 0 small.peek() nums[i]) {// 因为nums[i] 是可能小于small.peek()的 我们没法直接删除nums[i] 所以要标记一下smallMark.merge(nums[i], 1, Integer::sum);// 从small里删除nums[i]smallSiz--;sum - nums[i];} else {// nums[i]不在前k-2小里 bigMark.merge(nums[i], 1, Integer::sum);bigSiz--;// 这里是为了使得small的数量变成k-3个 也就是还差一个才够k-2个// 是为了方便后面的操作// 从small里选一个放到big里int tmp small.poll();smallSiz--;sum - tmp;big.add(tmp);bigSiz;}// 先放到big里 然后从big里面拿一个放到small就刚好k-2个if (idist n) {big.add(nums[idist]);bigSiz;}// 要从big里拿一个 访问big.peek()之前要先更新bigupdateBigPeek();int tmp big.poll();bigSiz--;sum tmp;small.add(tmp);smallSiz;res Math.min(res, nums[i] nums[0] sum);}return res;}// 每次访问small.peek()之前都要先更新smallpublic void updateSmallPeek() {// 如果small.peek()已经被删除了 那么就把它从small里移除 直到small.peek()是未被删除的元素while (smallSiz 0 smallMark.getOrDefault(small.peek(), 0) 0) {int tmp small.poll();smallMark.merge(tmp, -1, Integer::sum);}}public void updateBigPeek() {while (bigSiz 0 bigMark.getOrDefault(big.peek(), 0) 0) {int tmp big.poll();bigMark.merge(tmp, -1, Integer::sum);}}
}
这个方法高效地使用了堆结构来保持每次窗口移动后都能快速地选择出当前窗口中的k-2个最小数而HashMap的标记删除机制则可以绕过优先队列不支持直接删除的限制。通过这个算法你可以在移动窗口的过程中不断更新当前窗口的最小值和最终得到包含nums[0]在内的最小成本和。 思考1为什么要用大顶堆只用小顶堆会怎么样? 因为小顶堆只能让您迅速访问堆中的最小值而不是最大值。因此如果窗口中有一个更小的数字需要加入到已满的小顶堆中这时候我们需要替换掉小顶堆中最大的数字您需要一种方式来找到小顶堆中的最大值而大顶堆允许我们做到这一点。 思考2bigMark.merge(tmp, -1, Integer::sum)这个是干什么 在Java中的 PriorityQueue 并没有提供直接删除特定元素的操作而是只提供了删除堆顶元素的操作。为了解决这个问题bigMark 的用途是实现“延迟删除”这个技巧通常在优先队列中删除非顶部元素时使用。 bigMark 是一个 HashMap它的键是元素值值是该元素被标记删除的次数。当我们要从优先队列 big 中删除一个元素时我们不能直接删除它因为它可能不在堆顶。所以我们在 bigMark 中对这个元素的删除次数加一。这个标记表示元素已经被逻辑上删除尽管它仍在优先队列中。merge 方法是一个合并函数它会检查 HashMap 中是否存在键 tmp 如果存在它会使用提供的合并函数 Integer::sum 将当前值与给定值相加。如果没有找到键 tmp它会插入键值对 tmp - -1。在这个场景中merge 方法用 -1 更新 tmp 的删除次数。每次 tmp 出现在堆顶时这个标记都会被检查。如果标记表示该元素被删除即删除计数大于零这个元素将会从堆中弹出同时更新它在 bigMark 中的标记。 // 假设堆中有一个元素值为 5现在我们要删除它
int tmp 5;
bigMark.merge(tmp, 1, Integer::sum); // 标记 tmp 为已删除// 当我们后续从堆中得到堆顶元素时
updateBigPeek(); // 在访问堆顶前更新堆// updateBigPeek 的实现会检查堆顶元素是否被标记为已删除如果是就将其从堆中移除
// 并在 bigMark 中更新其计数
public void updateBigPeek() {while (bigSiz 0 bigMark.getOrDefault(big.peek(), 0) 0) {int tmp big.poll(); // 弹出堆顶元素bigMark.merge(tmp, -1, Integer::sum); // 更新 bigMark减少删除计数}
}
