原创公众号：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:

输入: 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;
   }

下周继续！持续更新ing。欢迎关注公众号：bigsai,一起打卡力扣。还给大家准备一些干货，一起进步！

问题

最近打google的apactest，遇到一个经典的（但我不熟的）问题——给你一堆整数区间（比如[1, 3], [2, 6], [8, 10]），问它们合并后是怎样的？ 

比如上述三个区间合并后就变成：[1, 6], [8, 10]。

这个问题在leetcode上的难度评级是Hard，简直亮瞎啊，其实并不难呀：https://leetcode.com/problems/merge-intervals/ 


思路1

如果，区间的端点的范围很小，比如都在[0, 9999]，那很简单地开个bool数组，然后对于每个区间覆盖到的点都赋值为true，最后的区间就是那些连续一片一片的true，比如上述的三个区间的话，bool数组将是这样的：0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0,…把这些连续的true的端点提取出来就是合并后的区间啦！

这样做的限制是： 

1. 区间的范围得较小，不然没法开数组； 

2. 区间的平均跨度不是很大或区间的数量不多。

为什么会有2这条限制呢？先算一下这样做的复杂度： 

假设区间的平均跨度为L，有N个区间，所有区间端点的范围的长度为M，那么时间复杂度就是O(L*N + M)。如果L很大并且N很大，跟M一个数量级的话，那么这个算法将会超级慢的！



思路2

想法是很容易出来的，我们先按区间的左端点排序（不要问为什么，因为直觉，不排序的话，基本没法做啊）。

然后维护一个left和right值，表示当前已有的连续区间的左端点和右端点，它们的初始值自然就是第一个区间的端点值啦，还是拿上面的那三个区间作为例子。


  
第一步：[1, 3]，则left = 1, right = 3 

  第二步：[2, 6]，发现2还是小于right的，说明当前这个区间和前面的还是“连在一起的”，所以left值不用变，只需要更新right值就好了，right明显等于max(3, 6) = 6。 

  第三步，[8, 10]，发现8比right大，所以当前这个区间和前面的区间是“断开”的，前面的区间独立作为一个，然后left和right都从这个区间开始，嗯。


最后的结果自然是：[1, 6]，[8, 10]啦～

分析一下时间复杂度，排序的时候是O(NlogN)，然后线性扫一遍是O(N)，所以总的时间复杂度是O(NlogN)，跟区间的跨度没关系，跟区间端点的覆盖范围也没一毛钱关系！ 
只跟区间的个数有关系，而且还是很可以接受的一个复杂度（毕竟log N跟常数的区别不是很大）。



代码

只给出第二种思路的代码，第一种太过简单，不用了吧：



#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef vector<pair<int, int> > RangeList;

RangeList cover(const RangeList& intervals) {
    int left = intervals[0].first, right = intervals[0].second;
    RangeList result;

    for (int i = 1; i < intervals.size(); ++i) {
        // 前面自成一个区间，那么就此分开
        if (intervals[i].first > right) {
            result.push_back(make_pair(left, right));
            left = intervals[i].first;
            right = intervals[i].second;
        } else if (intervals[i].second > right) {
            right = intervals[i].second;
        }
    }
    result.push_back(make_pair(left, right));

    return result;
}

void display(const RangeList& intervals) {
    for (int i = 0; i < intervals.size(); ++i)
        cout << intervals[i].first << ' ' << intervals[i].second << endl;
    cout << endl;
}

int main() {
    RangeList intervals;
    int n, start, end;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> start >> end;
        intervals.push_back(make_pair(start, end));
    }
    sort(intervals.begin(), intervals.end());

    display(intervals);
    RangeList result = cover(intervals);
    display(result);

    return 0;
}

题目描述

实现思路
这道题力扣把它归为困难，只要理清了怎样合并的思路后就很简单了，合并思路：先建一个空的结果集列表，当前数组的第二个值比下一个数组的第一个值大，或者当前数组的第一个值比下一个数组的第二个值大，就把当前数组加入到结果集中。否则取当前数组的第一个值和下一个数组的第一个值的最小值赋值给下一个数组的第一个值，把当前数组的第二个值和下一个数组的第二个值的最大值赋值给下一个数组的第二个值。最后加上原列表集中最后一个列表即可。
代码
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        #如果intervals为空，返回newInterval
        if not intervals:
            return [newInterval]

        #记录intervals里每一个数组的第一个数字
        interval_fisrt=[]
        for i in range(len(intervals)):
            interval_fisrt.append(intervals[i][0])
        #记录newInterval应该插入的索引值
        j=0
        try:
            while interval_fisrt[j]<newInterval[0]:
                j+=1
        except IndexError:
            pass
        #插入newInterval
        intervals.insert(j,newInterval)
        
        #新建一个记录结果的列表
        result=[]
        for i in range(len(intervals)):
            try:
                #当前数组的第二个值比下一个数组的第一个值大，或者当前数组的第一个值比下一个数组的第二个值大，就把当前数组加入到结果集中
                if intervals[i][1]<intervals[i+1][0] or intervals[i][0]>intervals[i+1][1]:
                    result.append(intervals[i])
                #否则取当前数组的第一个值和下一个数组的第一个值的最小值赋值给下一个数组的第一个值
                #把当前数组的第二个值和下一个数组的第二个值的最大值赋值给下一个数组的第二个值
                else:
                    intervals[i+1]=[min(intervals[i][0],intervals[i+1][0]),max(intervals[i][1],intervals[i+1][1])]
            except IndexError:
                pass
        return result+[intervals[-1]]

欢迎一起讨论。

树链剖分，难点在于怎样维护答案区间。首先，这个题目啊。。。为了强行加上一个修改操作，害得我题都读不明白了。那个涨价就是顺带让你维护一个lazy。 最优解显然就是最大值-最小值啦，但是要有方向的。必须是在前面以最小值买，在后面以最大值卖。也就是一定是x->y的顺序。但是对应到线段树上，也许方向就反了，（毕竟x不一定编号小于y），因此我们在维护答案时，要注意方向。线段树每个区间只好记两个data了，分别表示正向的最优解和逆向的最优解，还要再记一个lazy维护区间修改。把最优解需要的信息记成一个结构体Data，重载运算符实现区间合并更方便。

#include<bits/stdc++.h>
using namespace std;
#define N 50010
#define inf 0x7fffffff
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,m,h[N],num=0,a[N];
int size[N],fa[N],dep[N],son[N];
int id[N],top[N],dfn=0,w[N];
struct edge{
    int to,next;
}data[N<<1];
struct Data{
    int x,mn,mx;
    Data(){x=0;mn=inf;mx=0;}
    Data operator+(Data b){
        Data res;
        res.mx=max(mx,b.mx);
        res.mn=min(mn,b.mn);
        res.x=max(x,b.x);
        res.x=max(res.x,b.mx-mn);
        return res;
    }
};
struct node{
    Data x,y;//x-- l->r最优解，y-- r->l最优解 
    int lazy;
}tree[N<<2];
void dfs1(int x){
    size[x]=1;
    for(int i=h[x];i;i=data[i].next){
        int y=data[i].to;
        if(fa[x]==y) continue;
        fa[y]=x;dep[y]=dep[x]+1;dfs1(y);size[x]+=size[y];
        if(size[y]>size[son[x]]) son[x]=y;
    }
}
void dfs2(int x,int tp){
    id[x]=++dfn;w[dfn]=a[x];top[x]=tp;
    if(son[x]) dfs2(son[x],tp);
    for(int i=h[x];i;i=data[i].next){
        int y=data[i].to;
        if(y==fa[x]||y==son[x]) continue;
        dfs2(y,y);
    }
}
inline void pushup(int p){
    tree[p].x=tree[p<<1].x+tree[p<<1|1].x;
    tree[p].y=tree[p<<1|1].y+tree[p<<1].y;
}
void build(int p,int l,int r){
    if(l==r){
        tree[p].x.mx=tree[p].y.mx=w[l];
        tree[p].x.mn=tree[p].y.mn=w[l];return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    pushup(p);
}
void pushdown(int p){
    if(!tree[p].lazy) return;
    tree[p<<1].lazy+=tree[p].lazy;tree[p<<1|1].lazy+=tree[p].lazy;
    tree[p<<1].x.mx+=tree[p].lazy;tree[p<<1|1].x.mx+=tree[p].lazy;
    tree[p<<1].x.mn+=tree[p].lazy;tree[p<<1|1].x.mn+=tree[p].lazy;
    tree[p<<1].y.mx+=tree[p].lazy;tree[p<<1|1].y.mx+=tree[p].lazy;
    tree[p<<1].y.mn+=tree[p].lazy;tree[p<<1|1].y.mn+=tree[p].lazy;
    tree[p].lazy=0;
}
Data query(int p,int l,int r,int x,int y,bool f,int v){
    if(x<=l&&r<=y){
        tree[p].lazy+=v;tree[p].x.mn+=v;tree[p].x.mx+=v;
        tree[p].y.mn+=v;tree[p].y.mx+=v;
        return f?tree[p].x:tree[p].y;
    }
    int mid=l+r>>1;pushdown(p);Data res;
    if(x<=mid) res=res+query(p<<1,l,mid,x,y,f,v);
    if(y>mid) res= f?res+query(p<<1|1,mid+1,r,x,y,f,v):query(p<<1|1,mid+1,r,x,y,f,v)+res;
    pushup(p);
    return res;
}
void solve(int x,int y,int v){
    Data ansl,ansr;
    while(top[x]!=top[y]){
        if(dep[top[x]]>=dep[top[y]]){
            ansl=ansl+query(1,1,n,id[top[x]],id[x],0,v);//0-- x->top[x]
            x=fa[top[x]];
        }
        else{
            ansr=query(1,1,n,id[top[y]],id[y],1,v)+ansr;//1-- top[y]->y
            y=fa[top[y]];
        }
    }
    if(id[x]<id[y]) ansl=ansl+query(1,1,n,id[x],id[y],1,v);
    else ansl=ansl+query(1,1,n,id[y],id[x],0,v);
    ansl=ansl+ansr;
    printf("%d\n",ansl.x);
}
int main(){
//  freopen("a.in","r",stdin);
    n=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<n;++i){
        int x=read(),y=read();
        data[++num].to=y;data[num].next=h[x];h[x]=num;
        data[++num].to=x;data[num].next=h[y];h[y]=num;
    }
    dep[1]=1;dfs1(1);dfs2(1,1);build(1,1,n);
    m=read();
    while(m--){
        int x=read(),y=read(),v=read();
        solve(x,y,v);
    }
    return 0;
}