[B] [C] [D]

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

In each round, pick two of the heaviest stones and smash them together. Suppose the stones weigh x and y, and x <= y. Then the possible results of shredding are as follows:

  • ifx == y“Then both stones will be completely shattered;
  • ifx ! = y, then the weight isxThe stone will shatter completely, and the weight isyThe new weight of the stone isy-x.

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

Example:

Input: [2,7,4,1,8,1] First 7 and 8 get 1, so the array is converted to [2,4,1,1,1], then 2 and 4 get 2, so the array is converted to [2,1,1,1], then 2 and 1 get 1, so the array is converted to [1,1,1], then 1 and 1 get 0, The final array is converted to [1], which is the weight of the remaining rock.Copy the code

Tip:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 1000

If the two values are not equal, insert the difference between them into the array and continue until the number of elements in the array is less than two. In this case, return the unique element value of the array or 0

So based on that, there are three ways to solve this problem

The sort order

Sort the array in ascending order, so that the two largest values are the two at the end of the array, and keep fetching the largest two values until the number of elements in the array is less than 2

The code is as follows:

Var lastStoneWeight = function(stones) {while(stones.length>1){sort(a,b); Const num1 = stones.pop(), num2 = stones.pop(); // If two numbers are not equal, insert the difference into the array if(num1! ==num2) stones.push(num1-num2); } return stones[0]||0; };Copy the code

Binary algorithm

We could just sort the array once, and then every time we have a difference, we could use the binary algorithm, find the first place in the array where the difference is greater than or equal to and insert it so we don’t have to sort the array every time

The code is as follows:

Var lastStoneWeight = function(stones) {stone.sort ((a,b) => a-b); While (stones.length>1){const num1 = stones.pop(), num2 = stones.pop(); // If the two numbers are not equal, insert the difference into if(num1! ==num2) stones = insert(stones,num1-num2); } function insert(arr,num){if(num<arr[0]) return [num,...arr] else if(num>arr[arr.leng-1]) return [...arr,num] let l = 0,r = arr.length-1; while(l<r){ const mid = (l+r)>>1; if(arr[mid]<num) l = mid+1 else r = mid; } // insert num into arr.splice(l,0,num); return arr; } return stones[0]||0; };Copy the code

Big pile top

So anything that involves maintaining a maximum, you can do it with a heap, and in this case we want to get the maximum value of the array, so we can do it with a big top heap, and the top element is the maximum value of the array and we’re going to take two of the maximum values of the heap and do it until the number of elements in the heap is less than two

The code is as follows:

Constructor (){this.arr = []; // Constructor (){this.arr = []; this.size = 0; } // Insert operation push(val){this.arr.push(val); this.size++; If (this.size>1){let cur = this.size-1, parent = (cur-1)>>1; while(cur>0&&this.arr[cur]>this.arr[parent]){ [this.arr[parent],this.arr[cur]] = [this.arr[cur],this.arr[parent]] cur = parent,parent = (cur-1)>>1; }} // pop(){if(this.size===0) return false; if(this.size===1){ this.size = 0; return this.arr.pop(); } const res = this.arr[0]; this.arr[0] = this.arr.pop(); this.size--; // pop down let cur = 0, childl = 1,childr = 2; while( (childl<this.size&&this.arr[childl]>this.arr[cur]) || (childr<this.size&&this.arr[childr]>this.arr[cur]) ){ if(childr<this.size&&this.arr[childr]>this.arr[childl]){ [this.arr[cur],this.arr[childr]] = [this.arr[childr],this.arr[cur]] cur = childr; }else{ [this.arr[cur],this.arr[childl]] = [this.arr[childl],this.arr[cur]] cur = childl; } childl = cur*2+1,childr = cur*2+2; } return res; // heap = new BigHeap(); // heap = new BigHeap(); For (let I = 0; i<stones.length; I ++){heap.push(stones[I])} while(heap.size>1){const num1 = heap.pop(), num2 = heap.pop(); // If there is a difference, insert the difference into the heap if(num1! ==num2) heap.push(num1-num2); } return heap.pop()||0; };Copy the code

At this point we are done with Leetcode-1046 – the weight of the last stone

If you have any questions or suggestions, please leave a comment!