LeetCode 55跳跃游戏&56合并区间&57插入区间-阿里云开发者社区

LeetCode 55跳跃游戏&56合并区间&57插入区间

2022-10-23 104

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

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

跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]

输出: true

解释: 我们可以先跳 1 步，从位置 0 到达位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]

输出: false

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

分析

这题我们可以使用一个O(n)的方法，和前面一些题的方法也很相似，遍历这个数组，遍历的同时用一个index标记最大值。如果可以更新最大值那么就更新，如果index比最大值还大，那就直接返回false。

可到达的：

不可到达的：

具体ac代码：

public boolean canJump(int[] nums) {
     boolean jud[]=new boolean[nums.length];
   int maxlen=nums[0];
   int index=0;
   while (index<nums.length) {
    if(index>maxlen)
      return false;
    if(index+nums[index]>maxlen)
    {
      maxlen=index+nums[index];
    }
    else {
      index++;
    }
  }
   return true;
   }

合并区间

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

示例 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] 可被视为重叠区间。

注意：输入类型已于2019年4月15日更改。请重置默认代码定义以获取新方法签名。

分析

思路都是一个思路，先把数组进行排序(根据左侧数据)，排完序的数组遍历从左往右记录left，right。

left，right初始为left=intervals[0][0],right=intervals[0][1]。
遍历的时候如果当前元素intervals[index][0]<right 那么将left，right添加到结果集中，重新赋值left，right初始为当前元素值。
如果intervals[index][0]>right条件下，如果 intervals[index][1]>right那么更新right为intervals[index][1]继续，否则继续向下。

在代码实现上提供两个版本，一个使用List的，一个用数组复用空间，使用List：

public int[][] merge(int[][] intervals) {
   if(intervals.length==0)return new int[0][0];
   Arrays.sort(intervals,new Comparator<int []>() {//排序
    @Override
    public int compare(int[] o1, int[] o2) {
      // TODO Auto-generated method stub
      return o1[0]-o2[0];
    }
  });
   List<Integer>list=new ArrayList<Integer>();
   int left=intervals[0][0],right=intervals[0][1];
   for(int i=1;i<intervals.length;i++)
   {
     if(intervals[i][0]<=right)
     {
       if(intervals[i][1]>right)
         right=intervals[i][1];
     }
     else {
      list.add(left);
      list.add(right);
      left=intervals[i][0];
      right=intervals[i][1];
    }
   }
   list.add(left);
   list.add(right);
   int val[][]=new int [list.size()/2][2];
   for(int i=0;i<list.size();i+=2)
   {
     val[i/2][0]=list.get(i);
     val[i/2][1]=list.get(i+1);
   }
   return val;
}

而复用数组实现思路如下：

 public int[][] merge(int[][] intervals) {
   if(intervals.length==0)return new int[0][0];
   Arrays.sort(intervals,new Comparator<int []>() {//排序
    @Override
    public int compare(int[] o1, int[] o2) {
      // TODO Auto-generated method stub
      return o1[0]-o2[0];
    }
  });
   int index=0;
   int left=intervals[0][0],right=intervals[0][1];
   for(int i=1;i<intervals.length;i++)
   {
     if(intervals[i][0]<=right)
     {
       if(intervals[i][1]>right)
         right=intervals[i][1];
     }
     else {
       intervals[index][0]=left;
       intervals[index][1]=right;
      index++;
       left=intervals[i][0];
       right=intervals[i][1];
    }
   }
   intervals[index][0]=left;
   intervals[index][1]=right;
   return Arrays.copyOf(intervals, index+1);
}

时间差不多6ms。

插入区间

给出一个无重叠的，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]

输出：[[1,5],[6,9]]

示例 2：

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]

输出：[[1,2],[3,10],[12,16]]

解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

注意：输入类型已在 2019 年 4 月 15 日更改。请重置为默认代码定义以获取新的方法签名。

和上一题的思想差不多，先排序是肯定的。只不过这里有一点变化：给一个新的数组区间插进来然后再进行合并，在处理上你可以每次遍历的时候和我们数组进行比较，但是那无疑是一个比较差的方法。所以在这里我先用二分定位到添加的那个区间在原数组中的位置，然后分两次遍历进行操作就可以啦。

具体代码为：

public int[][] insert(int[][] intervals, int[] newInterval) {
  if(intervals.length==0)
  {
    int val[][]= {{newInterval[0],newInterval[1]}};
    return val;
  }
  List<Integer>list=new ArrayList<Integer>();
  //二分找到位置
  int l=0,r=intervals.length-1;
  int index=0;
  while (l<r) {
    int mid=(l+r)/2;
    if(intervals[mid][0]==newInterval[0])
    {
      l=mid+1;r=mid-1;
    }
    else if(intervals[mid][0]<newInterval[0])
    {
      l=mid+1;
    }
    else {
      r=mid-1;
    }
  }
  index=l;
  int left=intervals[0][0],right=intervals[0][1];
  if(index==0) {
    left=newInterval[0];right=newInterval[1];
  }
  for(int i=0;i<index;i++)
  {
    if(intervals[i][0]<=right)
     {
       if(intervals[i][1]>right)
         right=intervals[i][1];
     }
     else {
      list.add(left);
      list.add(right);
      left=intervals[i][0];
      right=intervals[i][1];
    }
  }
  if(newInterval[0]<=right)
   {
     if(newInterval[1]>right)
       right=newInterval[1];
   }
   else {
    list.add(left);
    list.add(right);
    left=newInterval[0];
    right=newInterval[1];
  }
  for(int i=index;i<intervals.length;i++)
  {
    if(intervals[i][0]<=right)
     {
       if(intervals[i][1]>right)
         right=intervals[i][1];
     }
     else {
      list.add(left);
      list.add(right);
      left=intervals[i][0];
      right=intervals[i][1];
    }
  }
  list.add(left);
  list.add(right);
   int val[][]=new int [list.size()/2][2];
   for(int i=0;i<list.size();i+=2)
   {
     val[i/2][0]=list.get(i);
     val[i/2][1]=list.get(i+1);
   }
   return val;
   }

LeetCode 55跳跃游戏&56合并区间&57插入区间

跳跃游戏

合并区间

插入区间

热门文章

最新文章

相关电子书