java重量组件遮挡_leetcode1046(最后一块石头的重量)Java语言实现

求&＃xff1a;

每一回合&＃xff0c;从中选出两块 最重的 石头&＃xff0c;然后将它们一起粉碎。假设石头的重量分别为 x 和 y&＃xff0c;且 x <&＃61; y。那么粉碎的可能结果如下&＃xff1a;

如果 x &＃61;&＃61; y&＃xff0c;那么两块石头都会被完全粉碎&＃xff1b;

如果 x !&＃61; y&＃xff0c;那么重量为 x 的石头将会完全粉碎&＃xff0c;而重量为 y 的石头新重量为 y-x。

最后&＃xff0c;最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下&＃xff0c;就返回 0。

示例&＃xff1a;

输入&＃xff1a;[2,7,4,1,8,1]

输出&＃xff1a;1

解释&＃xff1a;

先选出 7 和 8&＃xff0c;得到 1&＃xff0c;所以数组转换为 [2,4,1,1,1]&＃xff0c;

再选出 2 和 4&＃xff0c;得到 2&＃xff0c;所以数组转换为 [2,1,1,1]&＃xff0c;

接着是 2 和 1&＃xff0c;得到 1&＃xff0c;所以数组转换为 [1,1,1]&＃xff0c;

最后选出 1 和 1&＃xff0c;得到 0&＃xff0c;最终数组转换为 [1]&＃xff0c;这就是最后剩下那块石头的重量。

提示&＃xff1a;

1 <&＃61; stones.length <&＃61; 30

1 <&＃61; stones[i] <&＃61; 1000

解&＃xff1a;

1、堆排序

构造大顶堆&＃xff0c;每次从堆出弹出2个元素&＃xff0c;然后放入2者的差值(0也可以放进去&＃xff0c;不会影响判断)&＃xff0c;当堆中只有1个元素时返回。

时间复杂度&＃xff1a;O(NlogN)

空间复杂度&＃xff1a;O(N)

public intlastStoneWeight(int[] stones) {

Queue q &＃61; newPriorityQueue<>((integer,t1) -> t1 - integer);for(inti &＃61; 0;i

q.offer(stones[i]);}

while(q.size() > 1) {

Integer t1 &＃61; q.remove();Integer t2 &＃61; q.remove();q.offer(Math.abs(t1 - t2));}

returnq.remove();}

2、直接对原始数组排序

每次都在for循环内部&＃xff0c;将最大的2个元素放到数组末尾&＃xff0c;然后进行运算&＃xff0c;差值放数组末尾&＃xff0c;数组倒数第二个元素变成0&＃xff0c;在下一次的排序过程中&＃xff0c;又会选出新一轮的最大和第二大的数放到数组末尾进行比较&＃xff0c;整个过程一共需要持续stones.length-1次&＃xff0c;最终返回数组最后一位的元素&＃xff0c;它就是最大的。

这种方法是一种原地排序的方法&＃xff0c;会改变原始数组。

时间复杂度&＃xff1a;O(N^2logN)

空间复杂度&＃xff1a;O(1)

public intlastStoneWeight(int[] stones) {

intindex &＃61; stones.length- 1;for(inti &＃61; 0;i

Arrays.sort(stones);stones[index] -&＃61; stones[index-1];stones[index-1] &＃61; 0;}

returnstones[stones.length-1];}