leetcode - [1049] Last Stone Weight II

2020/09/14

问题描述

We have a collection of rocks, each rock has a positive integer weight.

Each turn, we choose any two rocks and smash them together. 
Suppose the stones have weights x and y with x <= y.  The result of this smash is:

  • If x == y, both stones are totally destroyed;
  • If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left. 
Return the smallest possible weight of this stone (the weight is 0 if there are no stones left.)

提供一个整数数组,每个元素代表一块石头的重量。

每次从中挑选两块石头然后将其粉碎,假设x <= y,粉碎规则如下:

  • 如果x == y,那么两块石头均被完全粉碎。
  • 如果x != y,那么轻的那块石头x就会被完全粉碎,而重量为y的石头变成y - x

最后,最多会剩下一块石头,请返回其最小重量(如果没有石头剩下,则返回0)。

举个例子:

二维

Thanks @wzc1995

梳理下思路:

首先,我们求出数组元素总和的平均值t

然后,进行DP,我们需要明确f(i, t)的含义:

它是一个boolean值,代表最多挑选i件商品,总价值是否能达到t

最后,倒序遍历dp[l]数组,一旦遇到dp[l][i] = true,直接返回sum - 2 * i,否则返回sum

来看下实现:

class Solution {
    public int lastStoneWeightII(int[] stones) {

        int l = stones.length;
        int sum = IntStream.of(stones).sum();
        int t = sum >>> 1;
        var dp = new boolean[l + 1][t + 1];
        dp[0][0] = true;

        for (int i = 1; i <= l; i++){
            dp[i][0] = true;
            for (int j = 1; j <= t; j++){
                // 有容量
                if (j - stones[i - 1] >= 0){
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - stones[i - 1]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        
        for (int i = t; i >= 0; i--){
            if (dp[l][i]) return sum - 2 * i;
        }
        return sum;
    }
}

一维

来看下实现:

class Solution {
    public int lastStoneWeightII(int[] stones) {

        int l = stones.length;
        int sum = IntStream.of(stones).sum();
        int t = sum >>> 1;
        var dp = new boolean[t + 1];
        dp[0] = true;

        for (int s: stones){
            for (int j = t; j >= s; j--){
                dp[j] |= dp[j - s];
            }
        }
        
        for (int i = t; i >= 0; i--){
            if (dp[i]) return sum - 2 * i;
        }
        return sum;
    }
}

我们也可以在第一个循环中计算最大的中间值half

class Solution {
    public int lastStoneWeightII(int[] stones) {

        int l = stones.length;
        int sum = IntStream.of(stones).sum();
        int t = sum >>> 1;
        int half = 0;
        var dp = new boolean[t + 1];
        dp[0] = true;

        for (int s: stones){
            for (int j = t; j >= s; j--){
                dp[j] |= dp[j - s];
                if (dp[j]) half = Math.max(half, j);
            }
        }
        
        return sum - 2 * half;
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory