企业网站建设商城,卖备案域名被抓,wordpress word上传图片,阿里云网站备案注销1 答疑
1.1 什么是贪心算法的左最优与右最优
左最优和右最优是贪心算法中的两种策略#xff1a; 左最优 (Leftmost Greedy): 在每一步选择中#xff0c;总是选择最左边#xff08;最早出现的#xff09;可行的选项。 右…1 答疑
1.1 什么是贪心算法的左最优与右最优
左最优和右最优是贪心算法中的两种策略 左最优 (Leftmost Greedy): 在每一步选择中总是选择最左边最早出现的可行的选项。 右最优 (Rightmost Greedy): 在每一步选择中总是选择最右边最晚出现的可行的选项。
这两种策略是贪心算法中根据具体问题选择的不同方向。
1.2 这两种最优问题分别用什么方法解决
一般左最优可以采取边遍历边找出当前的最值 右最优不能向左最优一样通过左到右的遍历稍带最值所以一般需要预处理从右到左遍历并且将得到的最值存放到数组中。
2 “左最优” 类题目
左最优其实也是一种局部最优
2.1 字节笔试题
小明在玩一场通关游戏初始血量为1关卡有怪兽或者有血包正数就是血包可回血数负数说明是怪兽的伤害值当捡到血包时会加血量碰到怪兽时会掉血现在指定初始血量为x关卡是一个数组小明必须按照数组的顺序玩游戏当碰到一个怪兽时他可以选择将这个怪兽扔到数组末尾小明可以无限次地将怪兽移到数组末尾,问小明最少移动几次就能存活,如果无论怎么移动都不能存活则返回-1 假设关卡是这样的[-200,-300,400]则返回-1假如是这样的[200,100,-250,-60,-70,100]则返回1只需要把-250挪到尾部
思路当发现自己血量不足时就从当前已经遍历过的所有关卡中选择耗费血量最多的那个关卡并且放到最后一关如果即使这样挪开了耗血量最大的一关自身血量还是为负则直接返回-1说明无法通关 ———————————————— 版权声明本文为CSDN博主「xxx_520s」的原创文章遵循CC 4.0 BY-SA版权协议转载请附上原文出处链接及本声明。 原文链接https://blog.csdn.net/yxg520s/article/details/131989933 2.2 leetcode 1642. 可以到达的最远建筑
这样的贪心思路871题最低加油次数和630课程表III也有体现。
两种贪心策略均可 优先使用梯子梯子不够时选取差值最小的出堆改用砖头。(小根堆) 优先使用砖头砖头不够时选取消耗最大的出堆改用梯子。(大根堆) 解法一的理论复杂度应该是最低的。
class Solution {// 优先使用梯子梯子不够时选取差值最小的出堆改用砖头。(小根堆)public int furthestBuilding(int[] heights, int bricks, int ladders) {int n heights.length, sum 0;QueueInteger queue new PriorityQueue();for(int i 1; i heights.length; i) {int diff heights[i] - heights[i - 1];if(diff 0) {queue.offer(diff);if(queue.size() ladders) {sum queue.poll();}if(sum bricks)return i - 1;}}return n - 1;}// 优先使用砖头砖头不够时选取消耗最大的出堆改用梯子。(大根堆)public int furthestBuilding2(int[] heights, int bricks, int ladders) {int nheights.length;PriorityQueueIntegerpqnew PriorityQueue((o1,o2)-((int)o2-(int)o1));int suml0,sumb0;for(int i1;in;i){int diffheights[i]-heights[i-1];if(diff0){pq.add(diff);sumbdiff;if(sumbbricks){sumb-pq.poll();suml;}if(sumlladders){return i-1;}}}return n-1;}
}作者onion12138
链接https://leetcode.cn/problems/furthest-building-you-can-reach/description/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。2.3 LC871. 最低加油次数
2.3.1 解析
贪心 优先队列堆
我们可以模拟行进过程使用 n 代表加油站总个数idx 代表经过的加油站下标使用 remain 代表当前有多少油起始有 remain startFuel)loc 代表走了多远ans 代表答案至少需要的加油次数。只要 loc target代表还没到达经过目标位置我们可以继续模拟行进过程。每次将 remain 累加到 loc 中含义为使用完剩余的油量可以去到的最远距离同时将所在位置 stations[idx][0] loc 的加油站数量加入优先队列大根堆根据油量排倒序中。再次检查是否满足 loc target下次循环此时由于清空了剩余油量 remain我们尝试从优先队列大根堆中取出过往油量最大的加油站并进行加油同时对加油次数 ans 进行加一操作。使用新的剩余油量 remain 重复上述过程直到满足 loc target 或无油可加。容易证明该做法的正确性同样是消耗一次加油次数始终选择油量最大的加油站进行加油可以确保不存在更优的结果。作者宫水三叶
链接https://leetcode.cn/problems/minimum-number-of-refueling-stops/solutions/1639184/by-ac_oier-q2mk/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
class Solution {public int minRefuelStops(int target, int startFuel, int[][] stations) {// 使用优先队列承装所经过加油站的油PriorityQueueInteger q new PriorityQueue((o1, o2) - (o2 - o1));int ans 0, len stations.length;// 特判if (len 1) return startFuel target ? -1 : 0;int fuel startFuel;// 加进油箱的油(含使用过的)// 经过可以到达的所有的加油站背上里面的油for (int i 0; i len; i ) {while (fuel stations[i][0]) {Integer add q.poll();if (add null) return -1;fuel add;ans ;}q.offer(stations[i][1]);}// 已经经过所有的加油站仍未到达则用车油箱和后备箱里的所剩的fuel,以期到达while (fuel target) {Integer add q.poll();if (add null) return -1;fuel add;ans ;}return ans;}/**题目思路- 将路上的一个个加油站 视为 一桶桶的油每次经过的时候就把油带上放后备箱- 当油不够的时候取出后备箱所带的 最多的那桶油 加进油箱- 这样以来如若油箱和后备箱的油加起来都不够那么就到不了了*/// 方法二需要后处理public int minRefuelStops2(int target, int startFuel, int[][] stations) {PriorityQueueInteger q new PriorityQueue((a,b)-b-a);int restartFuel;int ans0;int nstations.length;int pos0;int idx0;while(postarget){if(re0){if(!q.isEmpty()ans0){req.poll();}else{return -1;}}posre;re0;while(idxnposstations[idx][0]){q.add(stations[idx][1]);}}return ans;}
}2.4 LC630. 课程表 III (同2.2的解题思想非常相似)
class Solution {public int scheduleCourse(int[][] courses) {Arrays.sort(courses, (a,b)-a[1]-b[1]);PriorityQueueInteger q new PriorityQueue((a,b)-b-a);int sum 0;for (int[] c : courses) {int d c[0], e c[1];sum d;q.add(d);if (sum e) sum - q.poll();}return q.size();}
}作者宫水三叶
链接https://leetcode.cn/problems/course-schedule-iii/solutions/1156693/gong-shui-san-xie-jing-dian-tan-xin-yun-ghii2/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。2.5 LC45. 跳跃游戏 II(左最优问题)
class Solution {public int jump(int[] nums) {int nnums.length;int curf0;int ans0;int ml0;// 遍历时稍带计算左侧局部最优for(int i0;in;i){if(curfn-1){return ans;}mlMath.max(ml,inums[i]);if(icurf){ans;curfml;}}return ans;}}2.6 股票问题121. 买卖股票的最佳时机虽然使用堆的方法不是最优解但是方便和其他题目对比得出最优解 // 使用堆维护最小值public int maxProfit(int[] prices) {int nprices.length;//表示到第i天时股票的历史最低点价格PriorityQueueIntegerpqnew PriorityQueue((o1,o2)-(o1-o2));int max0;for(int i0;in;i){pq.add(prices[i]);maxMath.max(max,prices[i]-pq.peek());}return max;}3 “右最优” 类题目
3.1 LC670. 最大交换
搞懂两个问题便可彻底理解本题的**右最优贪心核心**。
选择哪个数作为候选数与前面的数交换——将最靠后的数定为候选数若它之前出现了更大的数则更新候选数为该数。 选择哪个数与候选数交换——只有当候选数之前存在更小的数时才需要交换这两数。若更靠前的位置出现小于候选数的数则将它与候选数交换。
class Solution {public int maximumSwap(int num) {char[] cs String.valueOf(num).toCharArray();int n cs.length, max n - 1;int[] maxIdx new int[n]; // 记录每个数从当前位置往右的最大值索引for (int i n - 1; i 0; i--) {if (cs[i] cs[max]) max i;maxIdx[i] max;}for (int i 0; i n; i) { // 从前往后找到第一个最大值不是自己本身的数if (cs[i] ! cs[maxIdx[i]]) {char tmp cs[i];cs[i] cs[maxIdx[i]];cs[maxIdx[i]] tmp;return Integer.parseInt(new String(cs));}}return num;}
}4 同时涉及到左最优和右最优的题目
4.1 LC42 接雨水需要两边同时进行预处理
class Solution {public int trap(int[] height) {int n height.length;if (n 0) {return 0;}int[] leftMax new int[n];leftMax[0] height[0];for (int i 1; i n; i) {leftMax[i] Math.max(leftMax[i - 1], height[i]);}int[] rightMax new int[n];rightMax[n - 1] height[n - 1];for (int i n - 2; i 0; --i) {rightMax[i] Math.max(rightMax[i 1], height[i]);}int ans 0;for (int i 0; i n; i) {ans Math.min(leftMax[i], rightMax[i]) - height[i];}return ans;}
}作者力扣官方题解
链接https://leetcode.cn/problems/trapping-rain-water/solutions/692342/jie-yu-shui-by-leetcode-solution-tuvc/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
