LeetCode探索（01背包和贪心算法）

前言

昨天在做力扣探索的时候遇到了两道数组题，看到题目的时候就感觉不知道如何下手。
苦思冥想一番，最后去偷看了答案，发现是贪心算法和01背包。
因为之前听说面试中很少出贪心和背包问题的题目，所以本来打算直接跳过，但是后来一看代码，不长，那还是了解一下吧。

合并区间

题目地址：合并区间
题目大意：给出一个区间的集合，合并所有区间。

这道题我一开始想了很久，想用单调栈来实现，当一个数进入的时候，弹出所有小于等于这个数的栈元素。
但是遇到了一个问题，当栈中元素为[1,4]的时候，我再放入[1,4]会导致栈直接为空。
想了一会没有想到什么好的解决方案，于是就去偷瞄了一眼答案，发现我一开始就走歪了，合并区间是一道经典的贪心算法的题目。

解题思路：
对于这道题来说，我们应该首先将数组按左区间升序排序，如果左区间一样就按右区间降序排序。
这样我们遇到两个区间左区间相同的时候就可以直接跳过。
对于相邻的两个区间，假设这两个区间为int[] pre和int[] cur，如果pre的右区间大于cur的左区间也就是说pre[1] <= cur[0]，那么说明这两个区间是可以合并的。
合并之后的右区间由谁决定呢？
显然是两个区间中右区间比较大的那个。

所以我们不难得出如下代码：

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals == null || intervals.length == 0 || intervals[0].length == 0)
            return new int[0][0];
        int[][] res = new int[intervals.length][2];
        int index = 0;
        Arrays.sort(intervals,(v1,v2)->((v1[0]==v2[0]) ?v2[1]-v1[1]:v1[0]-v2[0]));
        for(int[] tmp:intervals){
            if(index != 0 && tmp[0] == res[index-1][0])
                continue;
            if(index == 0 || tmp[0] > res[index-1][1]){
                res[index++] = tmp;
            }else{
                res[index-1][1] = Math.max(tmp[1],res[index-1][1]);
            }
        }
        return Arrays.copyOf(res,index);
    }
}

---

最后一块石头的重量

题目地址：最后一块石头的重量

解题思路：
对于01背包问题，通常的做法是给出一个二维数组int[][] dp。
dp[i][[j]代表的是当背包容量剩下j，选择是否拿第i个物品（这边是第i个物品，实际中是item[i-1]，因为一般我们不说第0个物品，所以不要搞错了）之后背包最大的价值。
对于任意状态dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])。

那么这道问题和01背包有什么关系呢？
要使得最后一块石头的重量最小，我们可以把石头分成两堆，使得两堆的差最小。
也就是在背包上限为（总重量）/2的时候尽可能的取石头使得石头总重量最重（价值最高）。
那么我们不难得出如下代码：

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int i=0;i<stones.length;i++)	
            sum += stones[i];
        int length = stones.length+1;
        int width = sum/2;
        //这边要注意，数组dp[i][j]指的是第i-1个物品，所以不要写错了
        int dp[][] = new int[length][width+1];
        for(int i=1;i<length;i++){
            for(int j=1;j<=width;j++){
                    if( j >= stones[i-1])
                        dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-stones[i-1]]+stones[i-1]);
                    else
                        dp[i][j] = dp[i-1][j];
                }
            }
        return sum - 2*dp[length-1][width];
    }
}

一般对于01背包问题，我们最后可以用滚动数组来代替二维数组，但是要注意，当更新j的时候是从后向前更新的，这是因为后面的状态依赖二维数组下左边格子和上面格子的状态，代码如下：

    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int i=0;i<stones.length;i++)	
            sum += stones[i];
        int length = stones.length+1;
        int width = sum/2;
        int dp[]= new int[width+1];
        for(int i=1;i<length;i++){
        	//注意这边，从后向前更新
            for(int j=width;j>=0;j--){
                    if( j >= stones[i-1])
                        dp[j] = Math.max(dp[j],dp[j-stones[i-1]]+stones[i-1]);
                    else
                        dp[j] = dp[j];
                }
            }
        return sum - 2*dp[width];
    }