56. 合并区间

首先考虑只有两个区间的情况：

但是这6种情况可以合并成3种情况，就是上面的3种。首先先判断第一个区间的起始位置是否小于等于第二个区间的起始位置。如果不成立，则交换两个区间。

再考虑n个区间的情况，先将他们根据区间的起始位置排序，然后两两进行合并。

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(v,v1)->v[0]-v1[0]);
        int[][] res=new int[intervals.length][2];//
        int index=-1;
        for(int[] interval:intervals){
            if(index==-1||res[index][1]<interval[0]){
                res[++index]=interval;
            }else{
                res[index][1]=Math.max(res[index][1],interval[1]);
            }
        }
        return Arrays.copyOf(res,index+1);//
    }
}

【补充】
1、copyOf(T[] original, int newLength)方法：original——需要拷贝的原始数组；newLength——拷贝元素长度，如果超出原始数组的长度则补充默认值，如int型则补充0
2、在创建二维数组时，可以省略列的参数，但是不能省略行的参数

64. 最小路径和

这道题并不一定非要走直线，只要是每次都是向右或向下就行，要注意审题。
条件：
题目要求，只能向右或向下走，换句话说，当前单元格 (i,j) 只能从左方单元格 (i−1,j) 或上方单元格 (i,j−1)走到，因此只需要考虑矩阵左边界和上边界。
走到当前单元格 (i,j)的最小路径和 = “从左方单元格 (i−1,j)与 从上方单元格 (i,j−1)走来的 两个最小路径和中较小的 ” + 当前单元格值 grid[i][j]。具体分为以下 4 种情况：
当左边和上边都不是矩阵边界时： 即当i≠0i , j≠0时，dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]；
当只有左边是矩阵边界时： 只能从上面来，即当i=0,j≠0时， dp[i][j]=dp[i][j−1]+grid[i][j]；
当只有上边是矩阵边界时： 只能从左面来，即当i≠0,j=0时， dp[i][j]=dp[i−1][j]+grid[i][j]；
当左边和上边都是矩阵边界时： 即当i=0,j=0时，其实就是起点， dp[i][j]=grid[i][j]；

class Solution {
    public int minPathSum(int[][] grid) {
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(i==0&&j==0){
                    grid[i][j]=grid[i][j];
                }else if(i==0){
                    grid[i][j]=grid[i][j-1]+grid[i][j];
                }else if(j==0){
                    grid[i][j]=grid[i-1][j]+grid[i][j];
                }else{
                    grid[i][j]=Math.min(grid[i-1][j],grid[i][j-1])+grid[i][j];
                }
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}

不用创建一个新的二维数组来存储求得的和，直接遍历 grid[i][j]修改即可。这是因为：grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j] ；原 grid矩阵元素中被覆盖为 dp 元素后（都处于当前遍历点的左上方），不会再被使用到。