本文共 2955 字,大约阅读时间需要 9 分钟。
title: LeetCode中最后一块石头的重量题解
description: LeetCode中最后一块石头的重量题解-java tags:难度简单113收藏分享切换为英文接收动态反馈
有一堆石头,每块石头的重量都是正整数。
每一回合,从中选出两块 最重的 石头,然后将它们一起粉碎。假设石头的重量分别为 x
和 y
,且 x <= y
。那么粉碎的可能结果如下:
x == y
,那么两块石头都会被完全粉碎;x != y
,那么重量为 x
的石头将会完全粉碎,而重量为 y
的石头新重量为 y-x
。最后,最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下,就返回 0
。
示例:
输入:[2,7,4,1,8,1]输出:1解释:先选出 7 和 8,得到 1,所以数组转换为 [2,4,1,1,1],再选出 2 和 4,得到 2,所以数组转换为 [2,1,1,1],接着是 2 和 1,得到 1,所以数组转换为 [1,1,1],最后选出 1 和 1,得到 0,最终数组转换为 [1],这就是最后剩下那块石头的重量。
提示:
1 <= stones.length <= 30
1 <= stones[i] <= 1000
将数组进行排序升序,从最后开始遍历,计算相邻差值赋值给后一位,将0赋值给前一位,然后再排序,依次遍历,到最后计算数组中最后一个值即为最后一块石头的重量的大小
class Solution { public int lastStoneWeight(int[] stones) { // 对数组进行升序排序 Arrays.sort(stones); int index = stones.length - 1; // 从后遍历相邻元素差值,赋值给对应数组下标,并将前一个值赋值为0,排序,依次进行 for(int i = index; i > 0; i--){ stones[index] = stones[index] - stones[index-1]; stones[index - 1] = 0; Arrays.sort(stones); } // 数组最后一个元素即为最后一块石头的重量 return stones[stones.length - 1]; }}
将所有石头的重量放入最大堆中,每次依次从队列中取出最重的两块石头a,b ,必有a>=b,如果a>b,则将新石头a-b的差值放入最大堆中,如果a=b,则不会产生新石头,重复此过程,直到最大堆中的元素少于2块。
若最终剩下一块石头,则该石头即为最后一块石头的重量,返回该元素,若无石头剩下,最大堆为空,则返回0
class Solution { public int lastStoneWeight(int[] stones) { // 创建一个最大堆 PriorityQueuepq = new PriorityQueue ((a, b) -> b - a); // 遍历数组,将值依次放入最大堆中 for (int stone : stones) { pq.offer(stone); } // 遍历最大堆 while (pq.size() > 1) { // 取出两个元素a,b int a = pq.poll(); int b = pq.poll(); // 比较如a大于b,将其差值放入最大堆中 if (a > b) { pq.offer(a - b); } } // 如果最后最大堆为空,则最后一块石头重量为0.否则为最大堆中剩余的值 return pq.isEmpty() ? 0 : pq.poll(); }}
时间复杂度:O(nlogn),其中 n 是石头数量。每次从队列中取出元素需要花费 O(logn) 的时间,最多共需要粉碎 n−1 次石头。
空间复杂度:O(n)
使用递归解决问题,最后条件:如果数组长度为2,则值为两个元素之间的差值;如果长度为1,则值为此元素,对数组进行排序,如果之后最后两个元素不为0,则值为 最后两个元素的差值,每次令数组最后一个元素为相邻两个元素的差值,倒数第二个元素的值为0,依次递归下去,直到长度为2或者为1,
class Solution { public int lastStoneWeight(int[] stones) { // 如果长度为2,则值为两个元素的差值 if (stones.length == 2) { return Math.abs(stones[0] - stones[1]); } // 如果长度为1,则为此元素 if (stones.length == 1) { return stones[0]; } // 进行升序排序 Arrays.sort(stones); // 如果只有最后两个元素不为0 ,则值为最后两个元素得差值 if (stones[stones.length - 3] == 0) { return stones[stones.length - 1] - stones[stones.length - 2]; } // 最后一个元素的值为,最后一个元素的值与倒数第二个元素的差值 stones[stones.length - 1] = stones[stones.length - 1] - stones[stones.length - 2]; // 令倒数第二个元素的值为0 stones[stones.length - 2] = 0; // 递归这个函数 return lastStoneWeight(stones); }}
转载地址:http://nkwzi.baihongyu.com/