网站什么做,南昌网站建设哪家好,长沙微网站制作,网站建设需要的人才1049.最后一块石头的重量Ⅱ
有一堆石头#xff0c;用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合#xff0c;从中选出任意两块石头#xff0c;然后将它们一起粉碎。假设石头的重量分别为 x 和 y#xff0c;且 x y。那么粉碎的可能结果如…1049.最后一块石头的重量Ⅱ
有一堆石头用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下
如果 x y那么两块石头都会被完全粉碎如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。
最后最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下就返回 0。
示例 1
输入stones [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]这就是最优值。示例 2
输入stones [31,26,33,21,40]
输出5提示
1 stones.length 301 stones[i] 100
题解
这个题居然是个01背包这是我万万想不到的。
看解释我们只要把这个数组分成最接近元素和一半的两堆然后再减一下就可以得到碰撞后的最小值了是不是啊。
那不就是要求数组中的某个集合最接近某个值的问题吗。可以转成01背包的思想和416.分那个等和子集一样的思路。
代码如下
package com.offer;/*** author bwzfy* create 2024/4/12**/
public class _1049最后一块石头的重量Ⅱ {public static void main(String[] args) {System.out.println(lastStoneWeightII(new int[]{31, 26, 33, 21, 40}));}public static int lastStoneWeightII(int[] stones) {int sum 0;for (int i 0; i stones.length; i) {sum stones[i];}int target sum / 2;// 目标找出数组中的一组数据加起来的和最接近target01背包问题int[][] dp new int[stones.length][target 1];for (int i 1; i target; i) {if (stones[0] i) {dp[0][i] stones[0];}}for (int i 1; i stones.length; i) {for (int j 1; j target; j) {// 能装入石头if (stones[i] j) {dp[i][j] Math.max(dp[i - 1][j], stones[i] dp[i - 1][j - stones[i]]);} else {dp[i][j] dp[i - 1][j];}}}int heap1 dp[stones.length - 1][target];int heap2 sum - heap1;return Math.abs(heap1 - heap2);}}
