The cause was a weekly contest titled 1705. Maximum number of apples to eat

There is a special apple tree, n days in a row, several apples can grow every day. On the ith day, apples grow on the tree, which will rot and become unedible after days (that is, days + days). There may also be days when no new apples grow on the tree. Days [I] == 0 and days[I] == 0 You intend to eat at most one apple a day to maintain a balanced diet. Note that you can continue to eat apples after these n days. Give you two integer arrays of length n, days and apples, and return the maximum number of apples you can eat. Example: Apples = [1,2,3,5,2], days = [3,2,1,4,2]

  • On the first day, you eat the apple that comes out on the first day.
  • The next day, you eat an apple that grows the next day.
  • On the third day, you eat an apple that grows the next day. After that day, the apples of the third day will have rotted.
  • From the fourth day to the seventh day you will eat the apples that come out on the fourth day.

The description of eating apples from the fourth day to the seventh day is all about apples from the fourth day. I thought it was to record the greed of the remaining apples, but it should be

  • On the fourth day, eat an apple that grows on the fourth day.
  • On day five, four apples on day four are good for three days, two apples on day five are good for two days, so eat one apple on day five
  • On day six, four apples on day four are good for two days, one apple on day five is good for one day, so eat one apple from day five
  • On the seventh day, four apples from the fourth day are good for one day, so eat one apple from the fourth day
  • The eighth day, the fourth day of the three apples warranty zero days, no eat.

Problem.

To give priority to the apples that are going bad, there are three steps:

var eatenApples = function(apples, Days) {let aLen = apples. Length let eat = 0 let queue = [] // Let I = 0 // This is the current day // todo // 1, take today's apples // 2, throw away the bad apple // 3, return eat};

1. Collect apples

If (I < aLen && apples[I]) {let j = queue.length-1 while(j >= 0 && ((I +)) {let j = queue.length-1 Days [I]) < (queue[j] + days[j]]))) {// queue[j] = queue[j] j--} queue[j + 1] = i }

2. Throw bad apples

While (queue length > 0 && (apples [queue [0]] < = 0 | | I > = (queue [0] + days [queue [0]])) / / the first bad position out of apple or the first bad position have been shelf life) queue.shift()

3, eat

if(queue.length > 0) {
  apples[queue[0]]--
  eat++
}

The reason is that our priority queue implementation is a simple array with O(n) complexity for each insert and shift(). The next step is to implement a priority queue using binary heap.

Binary heap

Binary heap is essentially a complete binary tree, and it’s divided into a maximum heap and a minimum heap, where any parent is bigger than the value of its children, and a minimum heap, where any parent is smaller than the value of its children. The root node of the binary heap is called the top of the heap. The root node of the largest heap is the largest element of the heap, and the root node of the smallest heap is the smallest element of the heap. The operation of binary heap includes inserting node, deleting node and constructing binary heap. These three operations are all based on the floating and sinking of node



(Fig. Inserting and Deleting Nodes)

Let’s simply implement a minimum binary heap using arrays

function BinaryHeap() { this.list = [] } BinaryHeap.prototype = { push(data) { this.list.push(data) this._moveUp() }, pop() { const data = this.list[0] this.list[0] = this.list[this.list.length - 1] this.list.pop() this._moveDown(0) return data }, {let childIndex = this.list.length-1 let parentIndex = (childIndex - 1) >>> 1 let temp = this.list.length-1 let parentIndex = (childIndex - 1) >>> 1 let temp = this.list[childIndex] while(childIndex > 0 && temp < this.list[parentIndex]) { this.list[childIndex] = this.list[parentIndex] childIndex = parentIndex parentIndex = (parentIndex - 1) >>> 1 } this.list[childIndex] = temp }, List [parent] let child = 2 * parent + 1 while(child < 1) {let parent = index let temp = this.list[parent] let child = 2 * parent + 1 while(child < 2) This.list.length) {if(child < this.list.length - 1 &&this.list [child + 1] < this.list[child]) {// If there are two children, Child++} if(this.list[child] < temp) {this.list[parent] = this.list[child] parent = child child = 2 * parent + 1 } else { break } } this.list[parent] = temp } }

Binary heap push and pop are logn complexity, analogous to binary search, we are logn, can not use binary instead of MAO, can not. Because the logn of a binary heap is a search plus a substitution, and the logn of a binary search is only a search, and the substitution is n, so it can’t.

application

The following use of binary heap to rewrite the code, we only need to achieve the binary heap whether up and down the comparison of conditions to modify, repeat the code does not occupy the space, roughly the code is as follows

function BinaryHeap(compareArr) { this.list = [] this.compareArr = compareArr } BinaryHeap.prototype = { lessThan(index1, index2) { return (index1 + this.compareArr[index1]) < (index2 + this.compareArr[index2]) }, first() { return this.list[0] }, length() { return this.list.length }, push(data) { // ... }, pop() { // ... }, _moveUp() { // ... while(childIndex > 0 && this.lessThan(temp, this.list[parentIndex])) { // ... } / /... }, _moveDown(index) { // ... while(child < this.list.length) { if(child < this.list.length - 1 && this.lessThan(this.list[child + 1],this.list[child])) { child++ } if(this.lessThan(this.list[child], temp)) { // ... } else { break } } this.list[parent] = temp } } var eatenApples = function(apples, days) { let aLen = apples.length let eat = 0 let queue = new BinaryHeap(days) let i = 0 while(i < aLen || queue.length >  0) { if(i < aLen && apples[i]) { queue.push(i) } while( queue.length() > 0 && (apples[queue.first()] <= 0 || (queue.first() + days[queue.first()]) <= i) ) queue.pop() if(queue.length() > 0) { apples[queue.first()]-- eat++ } i++ }  return eat };

Binary heap version of the code and the original speed comparison



The numbers 2 and 3 in the figure, which compare the time of the binary heap version to that of the linear array, also improved from 56% to 92%

The number 1 is the recommit of the fastest answer, but there is one test case that failed, possibly the one before the supplement.

The final code looks really long, but it might be clearer to read if you take the binary heap out by itself.

— — — — — 2021/3/15 update — — — — — — —

The third question of the week,Maximum average pass rateThe problem is very simple, the difference between the test data of this problem, using the violent solution will timeout, it feels like binary heap is used to write greedy standard data structure, because you only need to deal with the most whatever element, namely the top element.

— — — — — 2021/3/15 — — — — — — — —

— — — — — 2021/4/19 update — — — — — — —

Brush so many weeks of competition, priority queue is a must, every time to copy the code after modifying the comparison conditions, yesterday saw a better version, copy down

class Heap { constructor(compare) { this.A = []; this.compare = compare; } size() { return this.A.length; } left(i) { return 2 * i + 1; } right(i) { return 2 * i + 2; } parent(i) { return i > 0 ? (i - 1) >>> 1 : -1; } isEmpty() { return this.size() === 0; } peek() { return this.A[0]; } heapifyDown(i) { let p = i; const l = this.left(i), r = this.right(i), size = this.size(); if (l < size && this.compare(l, p)) p = l; if (r < size && this.compare(r, p)) p = r; if (p ! == i) { this.exchange(i, p); this.heapifyDown(p); } } heapifyUp(i) { const p = this.parent(i); if (p >= 0 && this.compare(i, p)) { this.exchange(i, p); this.heapifyUp(p); } } exchange(x, y) { const temp = this.A[x]; this.A[x] = this.A[y]; this.A[y] = temp; } compare() { throw new Error('Must be implement! '); } } class PriorityQueue extends Heap { constructor(compare) { super(compare); } enqueue(node) { this.A.push(node); this.heapifyUp(this.size() - 1); } dequeue() { const first = this.A[0]; const last = this.A.pop(); if (first ! == last) { this.A[0] = last; this.heapifyDown(0); } return first; }}

The advantage of compare is that the function is a parameter, the parameter is fixed as a child, the parent node, in the use of different data types can be customized according to the requirements of the maximum and minimum heap —–2021/4/19