Lzyprime blog (Github) was created on December 31, 2020.qq and email: 2383518170

Leetcode notes

Topic describes

There is a pile of stones, each stone has a positive round weight.

Each round, pick two of the heaviest stones and smash them together. Suppose the weight of the stone is x and y, and x <= y. The possible results of crushing are as follows:

  • If x == y, both stones would be completely crushed;
  • If x! = y, then the stone of weight x will be completely crushed, and the new weight of the stone of weight y will be y minus x.

In the end, no more than one stone will be left. Returns the weight of the stone. If there are no stones left, return 0.

Example: Enter: [2.7.4.1.8.1] output:1Explanation: Choose first7 和 8,1, so the array is converted to [2.4.1.1.1], and then select2 和 4,2, so the array is converted to [2.1.1.1], followed by2 和 1,1, so the array is converted to [1.1.1]1 和 1,0, the final array is converted to [1This is the weight of the last remaining stone. Tip:1 <= stones.length <= 30
1 <= stones[i] <= 1000
Copy the code

Source: LeetCode link: leetcode-cn.com/problems/la… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

code

Heap row

  • 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(a); pq.pop(a);int ns = abs(pq.top() - v1);
      pq.pop(a);if (ns) pq.push(ns);
    }

    if (pq.empty()) return 0; else return pq.top();
  }
};
Copy the code

  • 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
}
Copy the code

  • 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)}}Copy the code

Pattern matching

@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)}
Copy the code
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)}}Copy the code

  • 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)}}Copy the code