1046. Last Stone Weight

leetcode easy

#array#csharp#easy#heap#leetcode#queue

Task

Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два самых тяжелых камня и разбиваем их вместе. Предположим, что два самых тяжелых камня имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y имеет новый вес y - x. В конце игры остается не более одного камня. Верните вес последнего оставшегося камня. Если камней не осталось, верните 0.

Пример:

Input: stones = [2,7,4,1,8,1]

Output: 1

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public int LastStoneWeight(int[] stones) {
        var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
        foreach (var stone in stones) {
            maxHeap.Enqueue(stone, stone);
        }
        
        while (maxHeap.Count > 1) {
            var first = maxHeap.Dequeue();
            var second = maxHeap.Dequeue();
            if (first != second) {
                maxHeap.Enqueue(first - second, first - second);
            }
        }
        
        return maxHeap.Count == 0 ? 0 : maxHeap.Dequeue();
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int LastStoneWeight(vector<int>& stones) {
        var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
        foreach (var stone in stones) {
            maxHeap.Enqueue(stone, stone);
        }
        
        while (maxHeap.size() > 1) {
            var first = maxHeap.Dequeue();
            var second = maxHeap.Dequeue();
            if (first != second) {
                maxHeap.Enqueue(first - second, first - second);
            }
        }
        
        return maxHeap.size() == 0 ? 0 : maxHeap.Dequeue();
    }
}

Java solution

matched/original

import java.util.Collections;
import java.util.PriorityQueue;

public class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int stone : stones) {
            maxHeap.add(stone);
        }
        
        while (maxHeap.size() > 1) {
            int first = maxHeap.poll();
            int second = maxHeap.poll();
            if (first != second) {
                maxHeap.add(first - second);
            }
        }
        
        return maxHeap.isEmpty() ? 0 : maxHeap.poll();
    }
}

JavaScript solution

matched/original

function lastStoneWeight(stones) {
    stones.sort((a, b) => b - a);
    
    while (stones.length > 1) {
        let first = stones.shift();
        let second = stones.shift();
        if (first !== second) {
            stones.push(first - second);
            stones.sort((a, b) => b - a);
        }
    }
    
    return stones.length ? stones[0] : 0;
}

Python solution

matched/original

import heapq

def lastStoneWeight(stones):
    stones = [-stone for stone in stones]
    heapq.heapify(stones)
    
    while len(stones) > 1:
        first = -heapq.heappop(stones)
        second = -heapq.heappop(stones)
        if first != second:
            heapq.heappush(stones, -(first - second))
    
    return -stones[0] if stones else 0

Go solution

matched/original

package main

import (
    "container/heap"
    "fmt"
)

func lastStoneWeight(stones []int) int {
    h := &IntHeap{}
    heap.Init(h)
    for _, stone := range stones {
        heap.Push(h, stone)
    }
    
    for h.Len() > 1 {
        first := heap.Pop(h).(int)
        second := heap.Pop(h).(int)
        if first != second {
            heap.Push(h, first - second)
        }
    }
    
    if h.Len() == 0 {
        return 0
    }
    return heap.Pop(h).(int)
}

type IntHeap []int

func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

Explanation

Algorithm

Создай максимальную кучу из массива камней.

Извлекай два самых тяжелых камня, разбивай их, и, если необходимо, возвращай оставшийся камень обратно в кучу.

Повторяй шаг 2, пока не останется один или ноль камней, и верни вес последнего оставшегося камня или 0, если камней не осталось.

😎