高端网站建设合同,东莞网站建设制作厂,大连住房和建设局网站,360免费建站空间目录
55.跳跃游戏
45.跳跃游戏||
452.用最少数量的箭引爆气球
435.无重叠区间
763.划分字母区间
56.合并区间 55.跳跃游戏
55. 跳跃游戏
中等
给你一个非负整数数组 nums #xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大…目录
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 1040 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 1040 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 处射出一支箭若有一个气球的直径的开始和结束坐标为 xstartxend 且满足 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 105points[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 105intervals[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 500s 仅由小写英文字母组成
先遍历一遍数组得到每一个字母的最后出现位置。
再次遍历数组记录当前区间中所有字母的最后出现位置的最大值当索引等于该最大值位置时说明当前区间中的所有字母在后边的数组中都不会出现故得到一个区间将长度存入结果集合中并记录该区间的最后位置用来计算下一个区间的长度
class Solution { // 方法将字符串划分为若干个子串使得每个子串中的所有字符都属于同一个字符集 public ListInteger partitionLabels(String s) { // 用于存储最终结果的列表每个元素代表一个分区的长度 ListInteger 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 104intervals[i].length 20 starti endi 104 思路首先对数组排序。从第二个区间开始遍历如果和前一个区间有交集就将该区间更新为与前一个区间的并集。如果和前一个区间没有交集则前一个区间为合并好的区间放入结果集合中如果遍历到最后一个区间直接将最后一个区间放入结果数组中。
class Solution { public int[][] merge(int[][] intervals) { // 根据区间的起始位置对数组进行排序 Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0])); // 用于存储合并后结果的列表 Listint[] 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()][]); }
}
