LeetCode Top100之55,56题

写于2019年5月27日

文章目录

[55. 跳跃游戏](https://leetcode.com/problems/jump-game/)① 题目描述② 相同题型—— [45. 跳跃游戏 II](https://leetcode.com/problems/jump-game-ii/)（1）顺向顺藤摸瓜（贪心算法）（2）逆向顺藤摸瓜 ③ 改进相似题型的求解（1）顺序顺藤摸瓜（2）逆序顺藤摸瓜（3）当前的最大距离是否超过当前i [56. 合并区间](https://leetcode.com/problems/merge-intervals/)① 题目描述② 先排序再合并

55. 跳跃游戏

① 题目描述

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。示例 1:

输入: [2,3,1,1,4] 输出: true 解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例 2:

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

② 相同题型—— 45. 跳跃游戏 II

（1）顺向顺藤摸瓜（贪心算法）

贪心算法，每次在可跳范围内选择可以使得跳的更远的位置。如下图，开始的位置是 2，可跳的范围是橙色的。然后因为 3 可以跳的更远，所以跳到 3 的位置。 如下图，然后现在的位置就是 3 了，能跳的范围是橙色的，然后因为 4 可以跳的更远，所以下次跳到 4 的位置。 发现，最后只需要跳2步，就可以达到末尾，意思是given > need。时间复杂度$O(n)$，代码如下： public int jump(int[] nums) { int end = 0; int maxPosition = 0; int step = 0; for (int i = 0; i < nums.length - 1; i++) { // 找到能跳的最远的位置 maxPosition = Math.max(maxPosition, nums[i] + i); if (i == end) {// 到达了目前能跳的边界，更新边界，步数加一。跳向的位置一定在边界内 end = maxPosition; step++; } } return step; }

（2）逆向顺藤摸瓜

假设能达到末尾，则从末尾开始往前推，找到能达到末尾的最远的那个位置作为新的末尾；以此类推，直到末尾的下标变为0。如下图，末尾位置是 1，从前往后遍历，发现能跳到末尾的最远位置是橙色的4，,因此橙色4是跳到末尾的那个位置。 将4作为末尾位置，从前往后遍历，能跳到4的最远位置是橙色的3。 将3作为末尾位置，从前往后遍历，能跳到3的最远位置是橙色的1，此时已经到达首位，说明跳跃已经完成！ 最坏的时间复杂度$O(n^2)$，代码如下： public int jump(int[] nums) { int step = 0; int last = nums.length - 1; while (last != 0) { for (int i = 0; i < last; i++) {// 从前往后遍历，找到的第一个符合要求的位置就是最远的，停止遍历 if (nums[i] >= last - i) {// 能跳的距离大于等于该位置和last之间的距离，说明该位置符合要求 last = i; step++; break; } } } return step; }

③ 改进相似题型的求解

（1）顺序顺藤摸瓜

45题是肯定能跳到末尾，要让你求解跳到末尾的最少step；而55题不一定能跳到末尾，要让你自己判断是否能达到末尾。如果采用45题的第一种解法，那么在循环遍历的过程中，如果能跳的边界小于下标i，说明不能到达下标i，肯定不能跳到末尾，直接退出遍历！直接改进45题第一种解法的代码，代码如下： public boolean canJump(int[] nums) { int end = 0; int maxPosition = 0; for (int i = 0; i < nums.length - 1; i++) { if (i > end) {// 能跳的边界小于下标i，说明不能到达该位置，肯定不能达到末尾 return false; } maxPosition = Math.max(maxPosition, nums[i] + i); if (i == end) { end = maxPosition; } } return maxPosition >= nums.length - 1; }

（2）逆序顺藤摸瓜

假设能跳到末尾，从后往前推，一定能推到下标为0；如果中途发现nums[i] < last-i，肯定不能跳到末尾。改进45题的第二种解法，代码如下： public boolean canJump(int[] nums) { int last = nums.length - 1; while (last != 0) { boolean flag = false; for (int i = 0; i < last; i++) { if (nums[i] >= last - i) { last = i; flag = true; break; } } // flag为false，说明没有找到满足条件的最远位置，即没有位置能跳到last位置，直接返回false if (!flag) { return false; } } return true; }

（3）当前的最大距离是否超过当前i

比如[0,3,1,1,4]，当到数字3时，当前的最大距离（能跳的距离的累积）为0，而下标i = 1，肯定不能从数字0跳到数字3。先比较当前的最大距离和下标i的大小关系，然后不小于下标i，说明能到达下标i处，更新最大距离。代码如下： public boolean canJump(int[] nums) { int max_sum = 0; for (int i = 0; i < nums.length; i++) { if (max_sum < i) { return false; } max_sum = Math.max(max_sum, nums[i] + i); } return true; }

56. 合并区间

① 题目描述

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

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

示例 2:

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

② 先排序再合并

为区间构造区间类，然后构造区间类的比较器，通过比较器对 List<Interval>进行排序。排序后的区间，只需要前后合并即可。代码如下： // 创建区间类 public class Interval { int start; int end; Interval(int start, int end) { this.start = start; this.end = end; } } public int[][] merge(int[][] intervals) { // 为区间类创建比较器 Comparator<Interval> comparator = new Comparator<Interval>() { @Override public int compare(Interval o1, Interval o2) { return o1.start - o2.start; } }; // 将二维数组转化为List List<Interval> intervalList = new ArrayList<>(); for (int i = 0; i < intervals.length; i++) { intervalList.add(new Interval(intervals[i][0], intervals[i][1])); } // 通过创建的区间类比较器，将List中的区间进行排序 Collections.sort(intervalList, comparator); // 遍历List，实现区间合并 for (int i = 0; i < intervalList.size() - 1; ) { // 区间可以合并，指针i不变，用新区间继续合并后面的区间 if (intervalList.get(i).end >= intervalList.get(i + 1).start) { intervalList.get(i).end = Math.max(intervalList.get(i).end, intervalList.get(i + 1).end); intervalList.remove(i + 1); } else { i++;// 区间不可以合并，移动指针i } } // 将List转换二维数组，返回结果 intervals = new int[intervalList.size()][2]; for (int i = 0; i < intervalList.size(); i++) { intervals[i][0] = intervalList.get(i).start; intervals[i][1] = intervalList.get(i).end; } return intervals; }