本次题目

55 跳跃游戏45 跳跃游戏II452 用最少数量的箭引爆气球435 无重叠区间763 划分字母区间56 合并区间

55 跳跃游戏

局部最优：不管每次跳多少步，取最大跳跃步数，若覆盖了终点，则返回true，否则最后返回false。注意：下次的取值需要从上一次覆盖的跳数中遍历，每移动一次就将覆盖范围向后更新。

class Solution {public boolean canJump(int[] nums) {//考虑特殊情况if(nums.length == 1) return true;//取最大跳跃步数int maxJump = nums[0];for(int i = 0; i <= maxJump; i++){//下次的取值需要从上一次覆盖的跳数中遍历，每移动一次就将覆盖范围向后更新maxJump = Math.max(maxJump, nums[i] + i);//若覆盖了终点，则返回trueif(maxJump >= nums.length - 1) return true;}//最后返回falsereturn false;}}

45 跳跃游戏II

同上55 跳跃游戏，但是需要最小跳跃次数。局部最优：计算当前位置的最大跳跃位置，然后在遍历该范围，依次计算下一次跳跃的最大跳跃位置，如果两个位置的最大跳跃位置都没覆盖终点，则需要跳一步（跳到覆盖范围大的位置），然后继续上述过程，直到覆盖终点。

class Solution {public int jump(int[] nums) {//考虑特殊情况if(nums.length == 1) return 0;//取当前最大跳跃步数int curMaxJump = 0;//取下一跳最大跳跃步数int nextMaxJump = 0;//记录跳数int count = 0;//这里设置为最大能到length-1方便计算count//遍历时curMaxJump到达length-1（i的最大）说明还需要跳多一跳//curMaxJump到达不了length-1说明已经覆盖到终点for(int i = 0; i < nums.length - 1; i++){//依次计算下一次跳跃的最大跳跃位置，收集最大的下一跳范围nextMaxJump = Math.max(nextMaxJump, nums[i] + i);//如果两个位置的最大跳跃位置都没覆盖终点，则需要跳一步（跳到覆盖范围大的位置）if(i == curMaxJump){curMaxJump = nextMaxJump;count++;}}//返回结果return count;}}

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

局部最优：先对数组进行排序（按起始位置或终止位置排序都可以，这里按起始位置排序）。如果当前气球的起始位置在上一个气球的终止位置之后，说明两个气球不重叠，需要两支弓箭；否则一支弓箭可以射掉两个气球，同时更新当前气球的最小右边界（方便下一个气球判断是否可以一支弓箭射掉三个气球）。注意：对二维数组按第一位进行排序Arrays.sort(要排序的二维数组, paringInt(o -> o[0]));

class Solution {public int findMinArrowShots(int[][] points) {//先对数组进行排序//（按起始位置或终止位置排序都可以，这里按起始位置排序）//不能这样排序，如果输入过大相减时会溢出，导致判断失误// Arrays.sort(points, (o1, o2) -> {// if(o1[0] == o2[0]) return o1[1] - o2[1];//return o1[0] - o2[0];// });//正确的排序Arrays.sort(points, paringInt(o -> o[0]));//定义弓箭数量，至少为1int count = 1;//遍历气球for(int i = 1; i < points.length; i++){//如果当前气球的起始位置在上一个气球的终止位置之后，//说明两个气球不重叠，需要两支弓箭if(points[i][0] > points[i - 1][1]){count += 1;}else{//同时更新当前气球的最小右边界//（方便下一个气球判断是否可以一支弓箭射掉三个气球）points[i][1] = Math.min(points[i][1], points[i - 1][1]);}}//返回结果return count;}}

435 无重叠区间

局部最优：先对数组进行排序（按下限或上限都可以，这里使用上限），然后从左向右遍历，记录不交叉区间的最大个数，则需要移除的最小区间个数等于区间总数减去不交叉区间的最大个数。遍历时选择左边界大于等于最小右边界中右边界更小的区间，将该右边界设为最小有边界进行下一轮选择。

class Solution {public int eraseOverlapIntervals(int[][] intervals) {//考虑特殊情况if(intervals.length == 1) return 0;//先对数组进行排序Arrays.sort(intervals, paringInt(o -> o[1]));//计数int count = 1;//定义最小右边界int right = intervals[0][1];//然后从左向右遍历，记录不交叉区间的最大个数for(int i = 1; i < intervals.length; i++){//遍历时选择左边界大于等于最小右边界中右边界更小的区间，//将该右边界设为最小有边界进行下一轮选择if(intervals[i][0] >= right){right = intervals[i][1];count++;}}//返回结果//需要移除的最小区间个数等于区间总数减去不交叉区间的最大个数return intervals.length - count;}}

763 划分字母区间

局部最优：先遍历字符串，统计每个字符最后出现的位置。然后再重新遍历字符串开始分割，在到达当前子串最后位置之前不断更新最后位置，直到到达最后位置则分割，分割后从下一位继续，直到遍历完字符串。

class Solution {public List<Integer> partitionLabels(String s) {//存放结果List<Integer> res = new LinkedList<>();//先遍历字符串，统计每个字符最后出现的位置int[] lastPlace = new int[26];char[] s_arr = s.toCharArray();for(int i = 0; i < s_arr.length; i++){lastPlace[s_arr[i] - 'a'] = Math.max(i, lastPlace[s_arr[i] - 'a']);}//定义最后位置int end = lastPlace[s_arr[0] - 'a'];//定义下一轮初始位置int start = 0;//然后再重新遍历字符串开始分割，要从0开始，可能会第一个字符单独分割for(int j = 0; j < s_arr.length; j++){//在到达当前子串最后位置之前不断更新最后位置if(lastPlace[s_arr[j] - 'a'] > end) end = lastPlace[s_arr[j] - 'a'];//直到到达最后位置则分割if(j == end){res.add(j + 1 - start);start = j + 1;}}//返回结果return res;}}

56 合并区间

局部最优：定义二维数组存放结果。 先对数组进行排序（按左边界或右边界都可以，这里按照左边界排序），然后遍历数组，定义上一个区间左右边界，如果当前左边界小于上一右边界的区间进行合并，合并后修改当前右边界为最大右边界（左边界还是最小）；如果当前左边界大于上一右边界，则将区间放入结果数组，同时修改上一右边界为最大右边界，修改上一左边界为最小左边界；继续下一轮，直到遍历完数组。 注意：只有当前左边界大于上一右边界时才说明之前的区间合并好了，取最小左边界和最大右边界加入结果数组。最后一个数组需要手动加入（不管合并还是不合并）。

class Solution {public int[][] merge(int[][] intervals) {//考虑特殊情况if(intervals.length == 1) return intervals;//定义二维数组存放结果List<int[]> res = new LinkedList<>();//先对数组进行排序Arrays.sort(intervals, paringInt(o -> o[0]));//定义上一个右边界int right = intervals[0][1];//定义上一个左边界int left = intervals[0][0];//遍历数组for(int i = 1; i < intervals.length; i++){//取左边界小于上一个右边界的区间进行合并，合并后修改当前右边界为最大右边界if(intervals[i][0] <= right){right = Math.max(right, intervals[i][1]);}else{//直接将上一区间放入结果数组res.add(new int[]{left, right});//如果当前左边界大于上一右边界，则当前右边界为最大右边界right = intervals[i][1];//修改左边界left = intervals[i][0];}}//最后一个数组手动加入res.add(new int[]{left, right});//返回结果return res.toArray(new int[res.size()][]);}}

力扣记录：贪心算法3较难(1)区间问题——55 跳跃游戏 45 跳跃游戏II 452 用最少数量的箭引爆气球 435 无重叠区间 763 划分字母区间 56 合并区间