LEETCODE 1049. Last Stone Weight II 解题思路分析

题目大意:

最后一块石头的重量 II

有一堆石头,每块石头的重量都是正整数。

每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

如果 x == y,那么两块石头都会被完全粉碎;
如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下,就返回 0。

示例:

输入:[2,7,4,1,8,1]
输出:1
解释:
组合 2 和 4,得到 2,所以数组转化为 [2,7,1,8,1],
组合 7 和 8,得到 1,所以数组转化为 [2,1,1,1],
组合 2 和 1,得到 1,所以数组转化为 [1,1,1],
组合 1 和 1,得到 0,所以数组转化为 [1],这就是最优值。

提示:

  1. 1 <= stones.length <= 30
  2. 1 <= stones[i] <= 1000

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1049

解题思路分析:

题目说两个石头遇到之后,重量小的会消失,重量大的剩下两个石头的重量之差。如果俩石头一样重,则同时消失。最后求出所有石头相遇之后剩下的那一个石头重量的最小值。其实简单来说,就是把这一组石头的重量附上加减号,求和最小的可能。再换句话说,我们可以将石头分成两部分(都是正整数),两部分分别求和,这两个和的差值最小的情况即为最优解。

这样问题就转化为:是否能找到n个数,他们的和最接近整体和的一半。进而题目就变成了另外一题 LEETCODE 416. Partition Equal Subset Sum 。他们的思路完全相同。

很多人把这种题目称为背包问题, LEETCODE 416. Partition Equal Subset Sum 的解法就是背包问题的典型模板。解决这类问题的关键是求和,确切的说,是需要求出所有数字能够组成的和的可能,然后再从这些和中选出一个最接近目标值的数字(小于等于目标值)即为答案。

如何求和,我们来举例说明,比如存在数组:

int[] A = [1, 2, 3];

我们循环数组的每一个数,看看他们有多少组合的情况:

// 先从数组中取出1,这时组成的和只有1种结果。
int[] sum = [1]; // A = [2, 3];
// 然后取出2,这时2自身是一种结果,2+1是一种结果。
int[] sum = [1](之前的结果) + [2, 3(2+1)](新的结果); // A = [3];
// 再取出3,这时3自身是一种结果,3加上之前的每一个结果也是结果
int[] sum = [1, 2, 3](之前的结果) + [3, 4(3+1), 5(3+2), 6(3+3)](新的结果); // A = [];
// 即:
int[] sum = [1, 2, 3, 3, 4, 5, 6]

虽然最终sum中有重复的结果,但这不影响我们解决背包问题。

再回到本题,我们不需要求出所有可能的和,我们需要的是最接近总和一半的数字,因此,还以上边的A数组为例,我们只需要找到是否存在一些数字的和最接近3(如果没有再找2,直到找到为止)。找到之后,说明当前有一组数的和为3,那么剩下的数的和应该为(totalSum – 3),进而两者的差值应该是 (totalSum – 3) – 3。

代码方面,我们使用一个dp数组来保存和出现的可能。

boolean[] dp;

其中dp[i]表示:是否存在一些数字的和为i。初始值dp[0]为true,i的最大值为数组总和的一半再加一(注意下标越界。因为我们需要dp数组长度为总和的一半)。

具体实现看下完整代码:

public int lastStoneWeightII(int[] stones) {
    int sum=0; // 先求总和
    for(int stone : stones){
        sum+=stone;
    }
    int target = sum / 2; // 求出总和的一半。我们的目标是找到一组数的和最接近target
    // 定义dp数组,长度为target+1
    // dp[i]表示,是否存在一组数的和为i
    boolean[] dp = new boolean[target+1];
    dp[0]=true;
    int max=0; // 最接近target的最大值
    for(int stone : stones){ // 循环所有石头的重量
        for(int i=target;i>=stone;i--){ // i代表重量和。
            // 当前石头重量为stone,如果存在(i-stone)这个和,
            // 那么(i-stone)+stone = i 也是一种和的可能。
            dp[i] = dp[i] || dp[i-stone];
            if(dp[i]){ // 如果存在一组数的和为i
                if(i==target){这个和等于target时,直接返回。
                    return sum - target - target;
                }
                max = Math.max(i, max); // 更新最近接target的最大值
            }
        }
    }
    return sum - max - max;
}

本题解法运行时间为1ms。

Runtime: 1 ms, faster than 99.12% of Java online submissions for Last Stone Weight II.

Memory Usage: 34 MB, less than 100.00% of Java online submissions for Last Stone Weight II.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1049-last-stone-weight-ii-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

LEETCODE 1049. Last Stone Weight II 解题思路分析》有1条回应

  1. Pingback引用通告: LEETCODE 1046. Last Stone Weight 解题思路分析 - LEETCODE从零刷LEETCODE从零刷

发表评论

您的电子邮箱地址不会被公开。