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)
    }
}