Record 1 algorithm problem

The weight of the last stone

Leetcode-cn.com/problems/la…

Take the two largest stones, destroy each other, and put the remaining weight back. Take the two largest stones again, destroy each other and put them back. Repeat the process.

You end up with the weight of at most one stone. Or 0.

  1. If it’s a violent solution, you just reorder the array when you put it back.

        function lastStoneWeight(stones) {
        // Sort first
        stones.sort((a, b) = > a - b)
        while (stones.length > 1) {
            // Take out the largest two
            const a = stones.pop() ?? 0
            const b = stones.pop() ?? 0
            / / propulsion
            stones.push(a - b)
            // Reorder
            stones.sort((a,b) = > a - b)
        }

        return stones.length > 0 ? stones[0] : 0
    }
Copy the code

  2. Use a large root heap

    What is the big root heap? The big root heap is the container for the largest number, and the top of the heap is the largest number. So when we do an array simulation, we want the array to be in ascending order, and the last element is the largest number.

        function lastStoneWeight(stones) {
        stones.sort((a,b) = > a - b)
        while(stones.length > 1) {
            // The last one subtracts the previous one, as long as the ascending order is guaranteed, it must be >=0
            const c = stones.pop() - stones.pop()
            / / back
            stones.push(c)
            let i = stones.length
            // Start traversing from the back to deal with the c just pushed in
            // It is already in ascending order, so when it stops, it means that c has found the correct position
            while(stones[i] < stones[i - 1]) {
                const temp = stones[i]
                stones[i] = stones[i - 1]
                stones[i + 1] = temp
                i--
            }
        }
        // There will be at most one last.
        return stones[0]????0
    }
Copy the code

    The end of the