1049. Last Stone Weight I I

1049. Last Stone Weight II #

题目 #

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 yhas 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.)

Example 1:

Input: [2,7,4,1,8,1]
Output: 1
Explanation: 
We can combine 2 and 4 to get 2 so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1 so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0 so the array converts to [1] then that's the optimal value.

Note:

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

题目大意 #

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

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

提示:

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

解题思路 #

  • 给出一个数组,数组里面的元素代表的是石头的重量。现在要求两个石头对碰,如果重量相同,两个石头都消失,如果一个重一个轻,剩下的石头是两者的差值。问经过这样的多次碰撞以后,能剩下的石头的重量最轻是多少?
  • 由于两两石头要发生碰撞,所以可以将整个数组可以分为两部分,如果这两部分的石头重量总和相差不大,那么经过若干次碰撞以后,剩下的石头重量一定是最小的。现在就需要找到这样两堆总重量差不多的两堆石头。这个问题就可以转化为 01 背包问题。从数组中找到 sum/2 重量的石头集合,如果一半能尽量达到 sum/2,那么另外一半和 sum/2 的差是最小的,最好的情况就是两堆石头的重量都是 sum/2,那么两两石头对碰以后最后都能消失。01 背包的经典模板可以参考第 416 题。

代码 #


package leetcode

func lastStoneWeightII(stones []int) int {
	sum := 0
	for _, v := range stones {
		sum += v
	}
	n, C, dp := len(stones), sum/2, make([]int, sum/2+1)
	for i := 0; i <= C; i++ {
		if stones[0] <= i {
			dp[i] = stones[0]
		} else {
			dp[i] = 0
		}
	}
	for i := 1; i < n; i++ {
		for j := C; j >= stones[i]; j-- {
			dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
		}
	}
	return sum - 2*dp[C]
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者