lzyprime 博客 (github)
创建时间：2020.12.31
qq及邮箱：2383518170
leetcode 笔记
题目描述
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/last-stone-weight
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
code
堆排
-
c++
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> pq(stones.begin(), stones.end());
while (pq.size() >= 2) {
int v1 = pq.top();
pq.pop();
int ns = abs(pq.top() - v1);
pq.pop();
if (ns) pq.push(ns);
}
if (pq.empty()) return 0; else return pq.top();
}
};
-
kotlin
import java.util.PriorityQueue
import kotlin.math.abs
class Solution {
fun lastStoneWeight(stones: IntArray): Int =
PriorityQueue<Int>(stones.size) { v1, v2 -> v2 - v1 }.apply {
addAll(stones.toList())
while (size > 1) when (val ns = abs(poll() - poll())) {
0 -> Unit
else -> offer(ns)
}
}.lastOrNull() ?: 0
}
-
scala
import scala.collection.mutable
object Solution {
def lastStoneWeight(stones: Array[Int]): Int = {
val q = mutable.PriorityQueue.from(stones)
while (q.size >= 2) {
(q.dequeue() - q.dequeue()).abs match {
case 0 => None
case v => q.enqueue(v)
}
}
q.lastOption.getOrElse(0)
}
}
模式匹配
@tailrec
def lastStoneWeight(stones: Array[Int]): Int = stones.sorted.reverse.toList match {case v1 :: v2 :: list => if(v1 == v2) lastStoneWeight(list.toArray)else lastStoneWeight(((v1 - v2) :: list).toArray) case list => list.lastOption.getOrElse(0)}
import scala.annotation.tailrec
object Solution {
@tailrec
def lastStoneWeight(stones: Array[Int]): Int = stones.sorted.reverse.toList match {
case v1 :: v2 :: list => if(v1 == v2) lastStoneWeight(list.toArray) else lastStoneWeight(((v1 - v2) :: list).toArray)
case list => list.lastOption.getOrElse(0)
}
}
-
Rust
use std::collections::BinaryHeap;
impl Solution {
pub fn last_stone_weight(stones: Vec<i32>) -> i32 {
let mut heap = BinaryHeap::from(stones);
while heap.len() >= 2 {
match heap.pop().unwrap() - heap.pop().unwrap() {
0 => (),
v => heap.push(v)
}
};
heap.pop().unwrap_or(0)
}
}
