原创公众号：
bigsai希望和优秀的你做朋友，感觉不错还请一键三连。
回复进群即可加入和200+人一起打卡。上周打卡：
LeetCode 47全排列Ⅱ&48旋转图像
LeetCode 49字母异位词分组&50pow(x,n)&51八皇后
昨日打卡：LeetCode打卡 52八皇后Ⅱ&53最大子序和&54螺旋矩阵
跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 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
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
合并区间
合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例 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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
而复用数组实现思路如下：
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);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
时间差不多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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
下周继续！持续更新ing。欢迎关注公众号：bigsai,一起打卡力扣。还给大家准备一些干货，一起进步！
文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。
原文链接：bigsai.blog.csdn.net/article/details/109556087