代码随想录 贪心算法-难度题目-区间问题

目录

55.跳跃游戏 

45.跳跃游戏||

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

435.无重叠区间 

763.划分字母区间

56.合并区间 

---

55.跳跃游戏 

55. 跳跃游戏

中等

给你一个非负整数数组 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 ， 所以永远不可能到达最后一个下标。

提示：

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

运用覆盖位置来求解此题，每到一个位置都去尝试更新cover的值（如果走此步比之前的覆盖位置更大的情况下），如果覆盖位置覆盖到了最后一个数，，表示可以从起点跳到终点，返回true。遍历的结束位置是覆盖位置的最大点，如果此时cover还没有覆盖到最后一个数，说明不能从起点跳到终点。

class Solution {  public boolean canJump(int[] nums) {  // cover变量用来记录当前能够到达的最远位置  int cover = 0;  // 如果数组只有一个元素，则显然可以从该位置跳到终点（自己），返回true  if(nums.length == 1){  return true;  }  // 遍历数组，直到到达当前能够到达的最远位置cover  for(int i = 0; i <= cover; i++){  // 更新当前能够到达的最远位置，取当前位置能够到达的最远位置i + nums[i]和当前已知的最远位置cover中的较大值  cover = Math.max(cover, i + nums[i]);  // 如果当前能够到达的最远位置cover已经大于等于数组长度减一（即已经能够到达或超过数组的最后一个位置），  // 则表示可以从起点跳到终点，返回true  if(cover >= nums.length - 1){  return true;  }  }  // 如果遍历完数组后仍然没有找到能够到达终点的路径，则返回false  return false;  }  
}

45.跳跃游戏||

45. 跳跃游戏 II

中等

给定一个长度为 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

提示:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000
• 题目保证可以到达 nums[n-1]

这里有nowcover和nextMaxCover两个变量，分别代表这一步能覆盖到的最远地点和下一步能覆盖到的最远地点 ，如果当前位置已经到了这一步能覆盖到的最远地点，跳出这一步，然后一步的nowcover换为在上一步中求得的nextMaxCover，继续向后遍历，如果nextMaxCover覆盖到了最后一个值，跳出这一步，到达最后一个值

class Solution {  public int jump(int[] nums) {  // 如果数组为空或者只有一个元素，则不需要跳跃，直接返回0  if(nums.length < 2 || nums == null){  return 0;  }  // 跳跃次数  int count = 0;  // 当前覆盖的最远位置  int nowCover = 0;  // 下一次跳跃能够覆盖的最远位置  int nextMaxCover = 0;  // 遍历当前覆盖位置中的每个位置  for(int i = 0; i <= nowCover; i++){  // 更新下一次跳跃能够覆盖的最远位置  nextMaxCover = Math.max(i + nums[i], nextMaxCover);  // 如果下一次跳跃能够直接到达数组末尾，则增加一次跳跃并跳出循环  if(nextMaxCover >= nums.length - 1){  count++;  break;  }  // 如果当前位置到达了当前能够覆盖的最远位置，说明需要进行一次跳跃  if(i == nowCover){  count++;  // 更新当前能够覆盖的最远位置为下一次跳跃能够覆盖的最远位置  nowCover = nextMaxCover;  }  }  // 返回跳跃次数  return count;  }  
}

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

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

中等

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。

提示:

• 1 <= points.length <= 105
• points[i].length == 2
• -231 <= xstart < xend <= 231 - 1

思路：用最少的箭射最多的气球

从第二个气球开始，因为之前已经排过序，直接比较第二个气球的最左侧和第一个气球的最右侧，如果第二个气球的最左侧更大，说明两个气球没有交集，需要一支箭来射第二个气球。否则第二个气球和第一个气球有交集，可用同一根箭射，因为第二支箭的最左侧一定大于第一支箭的最左侧，选择第一个气球和第二个气球的最后侧中的最小值，赋值给第二个气球，得到第二个气球的范围即为第一二个气球的交集，之后的第三个气球如果和第二个气球现在的范围有交集，则说明前三个气球和前两个气球可以用同一支箭射，以此类推。

class Solution {  // 方法：找到射穿所有气球所需的最少箭数量  public int findMinArrowShots(int[][] points) {  // 根据每个气球的水平位置x进行排序，如果x相同，则保持原顺序  Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));  // 初始化箭的数量为1，因为至少需要一支箭来射穿第一个气球  int count = 1;  // 遍历所有气球（从第二个开始，因为第一个已经有一支箭了）  for(int i = 1; i < points.length; i++){  // 如果当前气球的水平位置最左侧大于前一个气球的水平位置最右侧if(points[i][0] > points[i-1][1]){  // 则需要增加一支箭来射穿当前气球  count++;  }else{  // 如果当前气球与前一个气球有重叠 // 则更新当前气球的垂直位置y为两个气球中更小的y值  // 这样做是为了保证在后续的迭代中，如果还有气球在这个垂直范围内，它们也可以被这支箭射穿  points[i][1] = Math.min(points[i][1],points[i - 1][1]);  }  }  // 返回所需的箭的数量  return count;  }  
}

435.无重叠区间 

435. 无重叠区间

中等

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

提示:

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 104

思路： 首先对数组进行排序，从第二个开始遍历区间，如果区间和前一个区间有重合，这个时候我们要考虑删除该区间还是前一个区间，为了尽可能避免和后面的区间重合，我们留下结束位置更小的区间以求和下一个区间的开始位置保持距离。

class Solution {  // 方法：删除尽可能多的重叠区间，返回删除的数量  public int eraseOverlapIntervals(int[][] intervals) {  // 根据区间的起始位置进行排序，如果起始位置相同，则保持原顺序  Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));  // 初始化计数器，记录重叠区间的数量  int count = 0;  // 遍历所有区间（从第二个区间开始，因为第一个区间不需要比较）  for (int i = 1; i < intervals.length; i++) {  // 如果当前区间的起始位置小于前一个区间的结束位置，说明有重叠  if (intervals[i][0] < intervals[i - 1][1]) {  // 更新当前区间的结束位置为两个区间结束位置的较小值(这里相当于删除结束位置较大的区间) // 这样做是为了保留和下一个区间尽可能远的距离，避免和下一个区间重合intervals[i][1] = Math.min(intervals[i][1], intervals[i - 1][1]);  // 重叠区间数量加1  count++;  }  }  // 返回删除的重叠区间的数量  return count;  }  
}

763.划分字母区间

763. 划分字母区间

中等

提示

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

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

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

提示：

• 1 <= s.length <= 500
• s 仅由小写英文字母组成

先遍历一遍数组，得到每一个字母的最后出现位置。

再次遍历数组，记录当前区间中所有字母的最后出现位置的最大值，当索引等于该最大值位置时，说明当前区间中的所有字母在后边的数组中都不会出现，故得到一个区间，将长度存入结果集合中，并记录该区间的最后位置用来计算下一个区间的长度

class Solution {  // 方法：将字符串划分为若干个子串，使得每个子串中的所有字符都属于同一个字符集  public List<Integer> partitionLabels(String s) {  // 用于存储最终结果的列表，每个元素代表一个分区的长度  List<Integer> result = new ArrayList<>();  // 用于存储每个字符在字符串中最后出现的位置的数组  int[] charLastIndex = new int[27]; // 因为字符a到z共26个，再加上字符'a'的ASCII码值，所以数组大小为27  // 将字符串转换为字符数组，方便后续遍历  char[] sChar = s.toCharArray();  // 遍历字符串的每个字符，记录它们最后一次出现的位置  for (int i = 0; i < sChar.length; i++) {  charLastIndex[sChar[i] - 'a'] = i;  }  // 当前遍历到的字符在字符串中最后出现的位置  int nowLastIndex = 0;  // 上一个分区的结束位置//相当于第一个区间之前的区间在index为-1的时候结束  int lastEndIndex = -1;  // 遍历字符串的每个字符  for (int i = 0; i < sChar.length; i++) {  // 更新当前遍历到的字符集中所有字符在字符串中最后出现的位置  nowLastIndex = Math.max(nowLastIndex, charLastIndex[sChar[i] - 'a']);  // 如果当前位置是当前字符集中所有字符最后出现的位置  if (i == nowLastIndex) {  // 将当前分区长度（当前位置与上一个分区结束位置之差）加入结果列表  result.add(i - lastEndIndex);  // 更新上一个分区的结束位置为当前位置  lastEndIndex = i;  }  }  // 返回分区长度的列表  return result;  }  
}

56.合并区间 

56. 合并区间

中等

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

 思路：首先对数组排序。从第二个区间开始遍历，如果和前一个区间有交集，就将该区间更新为与前一个区间的并集。如果和前一个区间没有交集，则前一个区间为合并好的区间，放入结果集合中，如果遍历到最后一个区间，直接将最后一个区间放入结果数组中。

class Solution {  public int[][] merge(int[][] intervals) {  // 根据区间的起始位置对数组进行排序  Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));  // 用于存储合并后结果的列表  List<int[]> result = new ArrayList<>();  // 如果区间数组为空或只有一个区间，则无需合并，直接返回原数组  if (intervals.length < 2 || intervals == null) {  return intervals;  }  // 从第二个区间开始遍历（第一个区间不需要比较）  for (int i = 1; i < intervals.length; i++) {  // 如果当前区间的起始位置大于前一个区间的结束位置，说明两个区间没有重叠  if (intervals[i][0] > intervals[i - 1][1]) {  // 将前一个区间添加到结果列表中  result.add(intervals[i - 1]);  } else {  // 两个区间有重叠，合并这两个区间  // 更新当前区间的起始位置为两个区间中较小的起始位置  intervals[i][0] = intervals[i - 1][0];  // 更新当前区间的结束位置为两个区间中较大的结束位置  intervals[i][1] = Math.max(intervals[i][1], intervals[i - 1][1]);  }  // 如果是遍历的最后一个区间，则需要将其添加到结果列表中  // 因为如果两个区间有重叠，它们会在下一个循环迭代中被合并，当前区间不会在前面的迭代中被添加到结果列表  if (i == intervals.length - 1) {  result.add(intervals[i]);  }  }  // 将结果列表转换为数组并返回  return result.toArray(new int[result.size()][]);  }  
}