【贪心算法】（二）贪心算法区间问题及进阶习题

server/2024/10/18 9:28:50/

算法>贪心算法区间问题及进阶习题

  • 算法>贪心算法解决区间问题
    • 跳跃问题
      • 1. 跳跃游戏
      • 2. 跳跃游戏 Ⅱ
    • 重叠区间问题
      • 3. 用最少数量的箭引爆气球
      • 4. 无重叠区间
      • 5. 划分字母区间
      • 6. 合并区间
  • 其他问题
    • 7. 最大子序和
    • 8. 加油站
    • 9. 监控二叉树

算法>贪心算法解决区间问题

跳跃问题

  对于跳跃问题这一类问题，核心在于把我跳跃过后的覆盖范围，与具体怎么跳，跳几格关系不大。

1. 跳跃游戏

力扣链接

  给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置 可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：
输入： nums = [2,3,1,1,4]
输出： true
解释： 可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：
输入： nums = [3,2,1,0,4]
输出： false
解释： 无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

核心思想

  • 对于当前位置元素，跳几步无所谓，关键在于可跳的覆盖范围，即不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围

  • 那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点，每移动一个单位，就更新最大覆盖范围

  • 算法>贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围）

  • 整体最优解：最后得到整体最大覆盖范围，看是否能到终点

i 每次移动只能在 cover 的范围内移动，每移动一个元素，cover 得到该元素数值（新的覆盖范围）的补充，让 i 继续移动下去。

而 cover 每次只取 max(该元素数值补充后的范围, cover 本身范围)。

如果 cover 大于等于了终点下标，直接 return true 就可以了

程序实现

class Solution {
public:bool canJump(vector<int>& nums) {int cover = 0;if(nums.size() == 1)		 // 只有一个元素，就是能达到return true;for(int i = 0; i <= cover; i++)			// 注意这里是小于等于cover{cover = max(i + nums[i], cover);	// 得到最大的覆盖范围if(cover >= nums.size() - 1)			// 覆盖完所有return true;}return false;}
};

2. 跳跃游戏 Ⅱ

力扣链接

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i]
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]

示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:
输入: nums = [2,3,0,1,4]
输出: 2

核心思想

  • 本题与上述相似，但难不少，还是要看最大覆盖范围

  • 贪心的思路， 局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最少步数。

  • 从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数！

  • 需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖

  如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点，如图：

 
图中覆盖范围的意义在于，只要红色的区域，最多两步一定可以到！（不用管具体怎么跳，反正一定可以跳到）

程序实现

  从图中可以看出来，就是移动下标达到了当前覆盖的最远距离下标时，步数就要加一，来增加覆盖距离。最后的步数就是最少步数。

这里还是有个特殊情况需要考虑，当移动下标达到了当前覆盖的最远距离下标时

  • 如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。
  • 如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。
class Solution {
public:int jump(vector<int>& nums) {if(nums.size() == 1)return 0;int res = 0;		// 结果：跳跃次数int cur = 0;		// 当前覆盖范围int next = 0;		// 下一步覆盖范围for(int i = 0; i < nums.size(); i++){next = max(next, i + nums[i]);		    // 更新下一步覆盖最远距离下标if(i == cur)						    // 遇到当前覆盖最远距离下标{if(cur != nums.size()-1)		    // 如果还未到终点{res++;                          // 需要走下一步cur = next;                     // 更新当前覆盖最远距离下标（相当于加油了）if(next >= nums.size() - 1)	    // 当前覆盖最远距到达集合终点，不用做res++操作了，直接结束break;}}}return res;}
};

重叠区间问题

对于重叠区间而言，存在一样的模板：

  • 首先对内部区间进行排序，使临近的的区间靠在一起（左对齐排序）

  • 当前区间左边界：points[i][0]，当前区间右边界 points[i][1]

  • 上个区间左边界：points[i-1][0]，上个区间右边界 points[i-1][1]

  • 区间重叠：当前区间左边界 < 上个区间右边界（视题目情况取 == ），更新当前区间的右边界。

    if(points[i][0] <  points[i-1][1])	// 重叠points[i][1] = min(points[i-1][1], points[i][1]);

3. 用最少数量的箭引爆气球

力扣链接

  墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数

核心思想

局部最优： 当气球出现重叠，一起射，所用弓箭最少
全局最优： 把所有气球射爆所用弓箭最少

  • 对数据根据左边界进行排序，使其相邻的数据尽可能的靠在一起，重叠部分一起射

 

  • 区域不重叠： 新的气球区域左边界 > 旧气球的右边界，即 points[i][0] > points[i-1][1]，弓箭数+1，res++。

  • 区域重叠： 新的区域左边界 <= 旧的右边界，points[i][0] <= points[i-1][1]，则需要更新重叠区域的右边界，是两个区域右边界的最小值，min(points[i][0], points[i-1][1])

代码实现

class Solution {
public:static bool cmp(vector<int> &point1, vector<int> &point2){return point1[0] < point2[0];}int findMinArrowShots(vector<vector<int>>& points) {if (points.size() == 0) return 0;int result = 1; // points 不为空至少需要一支箭// 对气球起点从小到大排序sort(points.begin(), points.end(), cmp);for(int i = 1; i < points.size(); i++){if(points[i][0] > points[i-1][1])	// 气球i和气球i-1不挨着 注意不是 >=result++;						// 需要一支箭else								// 气球i和气球i-1挨着points[i][1] = min(points[i-1][1], points[i][1]);	// 更新重叠气球最小右边界}return result;}
};

4. 无重叠区间

力扣链接

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意: 可以认为区间的终点总是大于它的起点，且区间 [1,2] 和 [2,3] 不重叠。

核心思想

  • 本题是一个典型的区间重叠问题，根据上述区间问题，只需对区间进行左排序，再统计重叠区间个数即可

代码实现

class Solution {
public:static bool cmp(vector<int> &point1, vector<int> &point2){if(point1[0] == point2[0])return point1[1] < point2[1];return point1[0] < point2[0];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {int res = 0;sort(intervals.begin(), intervals.end(), cmp);int end = intervals[0][1];for(int i = 1; i < intervals.size(); i++){if(intervals[i][0] >= end)	// 无重叠end = intervals[i][1];else		{end = min(end,intervals[i][1]);		//有重叠 更新重叠右边界res++;}}return res;}
};

5. 划分字母区间

力扣链接

  字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：
输入：S = “ababcbacadefegdehijhklij”
输出：[9,7,8] 解释： 划分结果为 “ababcbaca”, “defegde”, “hijhklij”。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

核心思想
  在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。

可以分为如下两步：

  • 统计每一个字符最后出现的位置
  • 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点，如图：

程序实现

class Solution {
public:vector<int> partitionLabels(string s) {vector<int> res;// 统计当前区间的左右下标int left = 0;int right = 0;		int hash[27] = {0};			// 记录每个字母最远出现的位置for(int i = 0; i < s.size(); i++)hash[s[i] - 'a'] = i;for(int i = 0; i < s.size(); i++){right = max(right, hash[s[i] - 'a']);	// 更新右边界最远下标if(i == right)							// 遍历到有边界最远下标{res.push_back(right - left + 1);left = right + 1;}}return res;			}
};

6. 合并区间

力扣链接

给出一个区间的集合，请合并所有重叠的区间。

示例 :
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]

核心思想

  • 本题的本质还是判断重叠区间问题
  • 如果没有重叠就把原区间加入到 result 数组中，若有重叠就更新结果集中上一个区间的右边界值，达到合并的效果。

代码实现

class Solution {
public:static bool cmp(vector<int> &point1, vector<int> &point2){if(point1[0] == point2[0])return point1[1] < point2[1];return point1[0] < point2[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> res;// 区间集合为空直接返回if (intervals.size() == 0) return res; //排序 相邻的靠在一起sort(intervals.begin(), intervals.end(), cmp);// 第一个区间就可以放进结果集里，后面如果重叠，在result上直接合并res.push_back(intervals[0]);int end = intervals[0][1];for(int i = 1; i < intervals.size(); i++){if(intervals[i][0] <= res.back()[1])	// 有重叠// 合并 更新结果集区间的右边界 细节max 存在新的右边界比旧的小的情况res.back()[1] = max(res.back()[1], intervals[i][1]);	elseres.push_back(intervals[i]);			// 无重叠 放入区间}return res;}
};

其他问题

7. 最大子序和

力扣原题

  给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分

示例 ：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

思路

  • 局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。
  • 遍历 nums，从头开始用sum累积，如果sum一旦加上 nums[i]变为负数，应该舍弃之前的累加和，从下一个数开始重新累加
  • 贪心：累加和到负数就舍弃

代码实现

class Solution {
public:int maxSubArray(vector<int>& nums) {int max = INT32_MIN;int sum = 0;for(int i = 0; i < nums.size(); i++){sum += nums[i];if(sum > max)max = sum;if(sum <= 0)sum = 0;}return max;}
};

8. 加油站

力扣链接

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

暴力求解

  • 暴力的方法很明显就是O(n^2)的，遍历每一个加油站为起点的情况，模拟一圈。

  • 如果跑了一圈，中途没有断油，而且最后油量大于等于0，说明这个起点是ok的。

  • 暴力的方法思路比较简单，但代码写起来也不是很容易，关键是要模拟跑一圈的过程。

  • for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历，要善于使用while！

// 暴力求解 模拟每次加油过程 1个测试用例通不过，时间复杂度过大
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) 
{for(int i = 0; i < gas.size(); i++)			// 从第一个点开始{int rest = gas[i] - cost[i];			// 起点剩余的油int idx = (i + 1) % gas.size();			// 下一站while(rest > 0 && idx != i)				// 还没进入下一圈{rest = rest + gas[idx] - cost[idx];	//计算下一站的剩余idx = (idx + 1) % cost.size();		// 更新下一站的站点if(rest < 0)break;}if(rest >= 0 && idx == i)return i;							//一圈结束，还有油}return -1;
}

核心思想

  • 如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的，反之则无法跑完一圈。

  • 每个加油站的剩余量rest[i] = gas[i] - cost[i]，i 从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，那么起始位置从i+1算起，再从0计算curSum。

  • 那么局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。

代码实现

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) 
{int rest;int restTotal = 0;				// 一圈总剩余int curSum = 0;					// 跑过路的总剩余int start = 0;	for(int i = 0; i < gas.size(); i++){rest = gas[i] - cost[i];curSum += gas[i] - cost[i];restTotal += rest;if(curSum < 0){curSum = 0;start = i + 1;}}if(restTotal < 0)	return -1;		//说明怎么走都不可能跑一圈了else 				return start;
}

9. 监控二叉树

力扣链接

  给定一个二叉树，我们在树的节点上安装摄像头，节点上的每个摄影头都可以监视其父对象、自身及其直接子对象，计算监控树的所有节点所需的最小摄像头数量。

示例

核心思路

  • 我们发现示例中摄像头都没有放在叶子节点上，这是很重要的一个线索，因为如果把摄像头放在叶子节点上，就浪费了一层的覆盖。所以把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。

  • 头节点也都没有放，但头结点放不放摄像头也就省下一个摄像头， 叶子节点放不放摄像头省下了的摄像头数量是指数阶别的，因此选择从叶子节点向上遍历。

  • 从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！

  • 两个难点分析：
    （1）二叉树的遍历
    （2）如何隔两个节点放一个摄像头

  • 从下往上看，可以使用二叉树后续遍历的顺序

    int traversal(TreeNode* cur) {// 空节点，该节点有覆盖if (终止条件) return ;int left = traversal(cur->left);    // 左int right = traversal(cur->right);  // 右逻辑处理                            // 中return ;
}

如何隔两个节点放一个摄像头

  对于每个节点都有无覆盖，有摄像头和有覆盖三种状态之一，分别用0, 1，2表示这三种状态。

0：该节点无覆盖
1：本节点有摄像头
2：本节点有覆盖

终止条件：
  遇到空节点，空节点究竟是哪一种状态呢？ 空节点为有覆盖状态，父节点（叶子节点）则为无覆盖状态，这样就可以在叶子节点的父节点放摄像头了，那么则递归的终止条件程序如下：

// 空节点，该节点有覆盖
if (cur == NULL) return 2;

单层逻辑处理

  • 情况1：左右节点都有覆盖： 此时中间节点应该就是无覆盖，如下图

  • 情况2：左右节点至少有一个无覆盖： 则中间节点（父节点）应该放摄像头
    毕竟有一个孩子没有覆盖，父节点就应该放摄像头。

  • 情况3：左右节点至少有一个有摄像头： 那么其父节点就应该是有覆盖的状态

  • 情况4：头结点没有覆盖
    以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况，如图：

    递归结束之后，还要判断根节点，如果没有覆盖，result++，代码如下：

    nt minCameraCover(TreeNode* root) {result = 0;if (traversal(root) == 0) { // root 无覆盖result++;}return result;
}

代码实现

class Solution {
public:int result;int traversal(TreeNode* cur) {// 状态0：无覆盖// 状态1：有摄像头// 状态2：有覆盖if(cur == nullptr)		// 空节点 有覆盖状态 使得父节点为无覆盖状态return 2;// 后续遍历int left  = traversal(cur->left);		// 左int right = traversal(cur->right);		// 右// 中// 情况1: 左右都有覆盖，父节点无覆盖if(left == 2 && right ==2)return 0;// 情况2: 左右至少有一个无覆盖 父节点有摄像头if(left == 0 || right == 0){result++;return 1;}// 情况3: 左右至少有一个有摄像头 父节点有覆盖if(left == 1 || right == 1)return 2;return -1;}int minCameraCover(TreeNode* root) {result = 0;// 情况4: 根节点无覆盖if(traversal(root) == 0)result++;return result;}
};

http://www.ppmy.cn/server/116926.html

相关文章

springboot系列--自动配置原理

springboot系列--自动配置原理

一、容器功能 一、组件添加功能 一、Configuration Configuration有两种模式&#xff0c;Full模式与Lite模式。 1、配置 类组件之间无依赖关系用Lite模式加速容器启动过程&#xff0c;减少判断 2、配置类组件之间有依赖关系&#xff0c;方法会被调用得到之前单实例组件&#…
阅读更多...
Java进阶13讲__补充2/2

Java进阶13讲__补充2/2

1. 设计模式 1.1 什么是设计模式 1.2 单例设计模式 package com.itheima.a_单例_饿汉式;public class T1 {public static void main(String[] args) {new Thread(new Runnable() {Overridepublic void run() {Demo demo Demo.createDemo();System.out.println(Thread.curr…
阅读更多...
String存储原理

String存储原理

1.是什么 在Java中&#xff0c;String 是一种特殊的类&#xff0c;它是不可变的并且存储在堆内存中。为了理解 String 的存储原理&#xff0c;我们需要分解几个关键概念&#xff1a;不可变性、堆内存、字符串常量池和垃圾回收机制。下面我将详细解释这些概念并举例说明。 不可变…
阅读更多...
监听html元素是否被删除，删除之后重新生成被删除的元素

监听html元素是否被删除，删除之后重新生成被删除的元素

/*** 监听水印是否清除和修改*/ export function watermarkClear() {// 添加水印的盒子let box: any document.querySelector(.dplayer-video-wrap)// 水印let watermark: any document.querySelector(.dplayer-logo)// 观察器的配置&#xff08;需要观察什么变动&#xff09…
阅读更多...
前端基础面试题·第三篇——JavaScript（其三）

前端基础面试题·第三篇——JavaScript（其三）

1.字符串 (1) 常用方法 1.charAt(index) 返回指定位置的字符,若没找到&#xff0c;则返回空2.charCodeAt(index) 返回指定位置的unicode字符编码,若没找到&#xff0c;则返回空 3.String.concat(str1,str2) 连接多个字符串&#xff0c;并返回新字符串4.String.fromCharCode(co…
阅读更多...
Qt C++ Udp相关知识学习（一）

Qt C++ Udp相关知识学习（一）

文章目录 udp 单播消息，是什么意思特点：使用场景：例子：udp 广播消息，是什么意思特点：使用场景：示例：参考udp 单播消息，是什么意思 UDP 单播消息（UDP unicast）是指使用用户数据报协议（UDP）通过网络发送消息的过程，消息的接收者是单个特定的目标设备或IP地址。 特…
阅读更多...
简单示例，搞懂PowerBI的ALL()，ALLEXCEPT()和ALLSELECTED()的区别

简单示例，搞懂PowerBI的ALL()，ALLEXCEPT()和ALLSELECTED()的区别

假设我们有如下数据&#xff0c;我们来统计下各班级的人数 我们在报表页里加上 班级’二班‘ 的筛选条件&#xff0c;此时PowerBI已经自动为我们显示了各班级人数&#xff1a;一班有3人&#xff0c;二班有1人。 根据我们的筛选条件&#xff0c;我们的统计人数应该是按照筛选器&…
阅读更多...
数据结构应用实例(六)——最短路径

数据结构应用实例(六)——最短路径

Content: 一、题目描述二、算法思想三、代码实现四、小结 一、题目描述 实现求最短路径的两种算法&#xff1a;Dijsktra 算法和 Floyd 算法&#xff1b; 二、算法思想 Dijkstra算法 求一个点到图中其余节点的最短路径&#xff1b; 首先设置三个辅助数组&#xff1a;   (1) f…
阅读更多...
最新文章

Copyright @ 2022~2023