这是小川的第388次更新，第418篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第250题（顺位题号是1046）。有一个石头集合，每个石头都有一个正整数重量值。
每次，我们选择两块最重的岩石并将它们粉碎在一起。假设石头的重量为x和y，x <= y。粉碎的结果是：
-
如果x == y，两块石头都被完全粉碎;
-
如果x != y，重量为x的石头被完全粉碎，重量为y的石头具有新的重量y-x。
最后，剩下最多1块石头。返回这块石头的重量（如果没有留下石头，则返回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
02 第一种解法
根据题目的意思，我们需要干两件事情，第一，每次找到数组中最大的两个数进行值替换，比较大小，相等就全干掉，不相等就把较大的值替换为两者的差值，再把较小的干掉；第二，重复第一步，直到所有元素都被干掉或者最后只剩下一个元素。
思路：先将数组排序，统计其中值为0的元素个数，因为stones[i]的范围在[1,1000]，循环进行值替换（替换为0），直到最后数组中值为0的元素个数等于stones.length或者stones.length-1，才结束循环。如果数组最后一个元素不等于0，就返回此元素的值，反之返回0。
public int lastStoneWeight(int[] stones) {
int n = stones.length;
while (!(checkStones(stones) == n || checkStones(stones) == n-1)) {
if (stones[n-2] == stones[n-1]) {
stones[n-2] = 0;
stones[n-1] = 0;
} else {
stones[n-1] -= stones[n-2];
stones[n-2] = 0;
}
}
// 全是0，或者只有最后一个元素不为0
return stones[n-1] == 0 ? 0 : stones[n-1];
}
/**
* 统计数组stones中值为0的元素个数
* @param stones
* @return
*/
public int checkStones(int[] stones) {
Arrays.sort(stones);
int count = 0, n = stones.length;
for (int i=0; i<n; i++) {
if (stones[i] == 0) {
count++;
}
}
return count;
}
03 第二种解法
我们可以将第一种解法再简化下，不去计数的个数，依旧按照题目的规则进行替换0操作，效果一样。
public int lastStoneWeight2(int[] stones) {
int n = stones.length;
for (int i=0; i<n-1; i++) {
Arrays.sort(stones);
if (stones[n-2] == stones[n-1]) {
stones[n-2] = 0;
stones[n-1] = 0;
} else {
stones[n-1] -= stones[n-2];
stones[n-2] = 0;
}
}
// 全是0，或者只有最后一个元素不为0
return stones[n-1] == 0 ? 0 : stones[n-1];
}
04 第三种解法
在第一种解法和第二种解法中，每次循环都需要重新排序数组，能不能将此步骤省掉？
答案是可以的，利用优先队列来实现。
在初始化优先队列时，选择有Comparator作为参数的构造方法，选择其reverseOrder方法，倒序排序（从大到小），将数组中的元素入队列，然后开始循环处理。因为优先队列会自动排序，最大值永远在队首，第二大的值次之，将两者取出相减，如果两者之差大于0，就将差值入队列。最后判断队列是否为空，为空就返回0，不为空就返回队首的元素值。
public int lastStoneWeight3(int[] stones) {
PriorityQueue<Integer> pq = new
PriorityQueue<>(Comparator.reverseOrder());
for (int stone : stones) {
pq.offer(stone);
}
while (pq.size() > 1) {
int num = pq.poll() - pq.poll();
if (num > 0) {
pq.offer(num);
}
}
return pq.isEmpty() ? 0 : pq.peek();
}
05 小结
算法专题目前已连续日更超过七个月，算法题文章256+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论