【当前排名42710】挑战leetcode进入前1w名

李恒道

https://leetcode.cn/problems/design-circular-queue/submissions/592501444/
模拟题，总体来说不难

/**
 * @param {number} k
 */
var MyCircularQueue = function (k) {
  this.arr = new Array(k);
  this.start = 0;
  this.num = 0;
  this.k = k;
};

/**
 * @param {number} value
 * @Return {boolean}
 */
MyCircularQueue.prototype.enQueue = function (value) {
  if (this.num == this.arr.length) {
    return false;
  }
  let pos = (this.start + this.num) % this.k;
  this.arr[pos] = value;
  this.num++;
  return true
};

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.deQueue = function () {
  if (this.num == 0) {
    return false;
  }
  this.start++;
  this.start = this.start % this.k;
  this.num--;
  return true
};

/**
 * @return {number}
 */
MyCircularQueue.prototype.Rear = function () {
  if (this.num == 0) {
    return -1;
  }
  return this.arr[(this.start + this.num - 1) % this.k];
};

/**
 * @return {number}
 */
MyCircularQueue.prototype.Front = function () {
  if (this.num == 0) {
    return -1;
  }
  return this.arr[this.start];
};

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.isEmpty = function () {
  if (this.num == 0) {
    return true;
  }
  return false;
};

/**
 * @return {boolean}
 */
MyCircularQueue.prototype.isFull = function () {
  if (this.num == this.arr.length) {
    return true;
  }
  return false;
};

李恒道

https://leetcode.cn/problems/implement-queue-using-stacks/submissions/592582991/
这题不像简单题啊

var MyQueue = function () {
  this.in = [];
  this.on = [];
};

/**
 * @param {number} x
 * @Return {void}
 */
MyQueue.prototype.push = function (x) {
  this.in.push(x);
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function () {
  if (this.on.length == 0) {
    while (this.in.length !== 0) {
      this.on.push(this.in.pop());
    }
  }
  return this.on.pop();
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function () {
  if (this.on.length == 0) {
    while (this.in.length !== 0) {
      this.on.push(this.in.pop());
    }
  }
  return this.on[this.on.length - 1];
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function () {
  if (this.in.length == 0 && this.on.length == 0) {
    return true;
  }
  return false;
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */

李恒道

https://leetcode.cn/submissions/detail/592572281/
打卡题，简单

var largestCombination = function (candidates) {
    let ans=0;
  for (let index = 0; index < 32; index++) {
    let num = 0;
    for (const candidate of candidates) {
        if(candidate&(1<<index)){
            num++;
        }
    }
    ans=Math.max(ans ,num)
  }
  return ans
};

李恒道

https://leetcode.cn/problems/implement-stack-using-queues/submissions/592584396/
打完收工

var MyStack = function () {
  this.queue = [];
  this._queue = [];
};

/**
 * @param {number} x
 * @Return {void}
 */
MyStack.prototype.push = function (x) {
  while (this.queue.length !== 0) {
    this._queue.push(this.queue.shift());
  }
  this.queue.push(x);
  while (this._queue.length !== 0) {
    this.queue.push(this._queue.shift());
  }
};

/**
 * @return {number}
 */
MyStack.prototype.pop = function () {
  return this.queue.shift();
};

/**
 * @return {number}
 */
MyStack.prototype.top = function () {
    return this.queue[0]
};

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function () {
    if(this.queue.length !== 0){
        return false
    }
    return true
};

/**
 * Your MyStack object will be instantiated and called as such:
 * var obj = new MyStack()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.empty()
 */

李恒道

https://leetcode.cn/problems/number-of-ways-to-split-array/submissions/592773013/
终于快打卡30天了

var waysToSplitArray = function(nums) {
    const sum = nums.reduce((accumulator, currentValue) => accumulator + currentValue,0);
    let preSum=0;
    let ans=0
    for (let index = 0; index < nums.length-1; index++) {
       preSum+=nums[index];
       if(preSum>=sum-preSum){
        ans++
       }
    }
    return ans

};

李恒道

https://leetcode.cn/problems/design-circular-deque/submissions/592790101/
双端队列，两个指针来回划就ok了

/**
 * @param {number} k
 */
var MyCircularDeque = function (k) {
  this.arr = new Array(k).fill(0);
  this.start = 0;
  this.num = 0;
  this.k = k;
};

/**
 * @param {number} value
 * @Return {boolean}
 */
MyCircularDeque.prototype.insertFront = function (value) {
  if (this.num == this.k) {
    return false;
  }
  this.start--;
  if (this.start < 0) {
    this.start += this.k;
  }
  this.arr[this.start] = value;
  this.num++;
  return true;
};

/**
 * @param {number} value
 * @return {boolean}
 */
MyCircularDeque.prototype.insertLast = function (value) {
  if (this.num == this.k) {
    return false;
  }
  let end = (this.start + this.num) % this.k;
  this.arr[end] = value;
  this.num++;
  return true;
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteFront = function () {
  if (this.num == 0) {
    return false;
  }
  this.start++;
  if (this.start >= this.k) {
    this.start = 0;
  }
  this.num--;
  return true;
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteLast = function () {
  if (this.num == 0) {
    return false;
  }
  this.num--;
  return true;
};

/**
 * @return {number}
 */
MyCircularDeque.prototype.getFront = function () {
  if (this.num == 0) {
    return -1;
  }
  return this.arr[this.start];
};

/**
 * @return {number}
 */
MyCircularDeque.prototype.getRear = function () {
  if (this.num == 0) {
    return -1;
  }
  let end = (this.start + this.num-1) % this.k;
  return this.arr[end];
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.isEmpty = function () {
  if (this.num == 0) {
    return true;
  }
  return false;
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.isFull = function () {
  if (this.num == this.k) {
    return true;
  }
  return false;
};

李恒道

https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/submissions/592793754/
感觉上是堆问题

/**
 * @param {number[]} nums
 * @Return {number}
 */
class MaxHeap {
  constructor() {
    this.heap = [];
  }

  insert(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let element = this.heap[index];
      let parentIndex = Math.floor((index - 1) / 2);
      let parent = this.heap[parentIndex];

      if (parent >= element) break;

      this.heap[index] = parent;
      this.heap[parentIndex] = element;
      index = parentIndex;
    }
  }

  extractMax() {
    const max = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.sinkDown(0);
    }
    return max;
  }

  sinkDown(index) {
    const length = this.heap.length;
    const element = this.heap[index];
    while (true) {
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIndex < length) {
        leftChild = this.heap[leftChildIndex];
        if (leftChild > element) {
          swap = leftChildIndex;
        }
      }

      if (rightChildIndex < length) {
        rightChild = this.heap[rightChildIndex];
        if (
          (swap === null && rightChild > element) ||
          (swap !== null && rightChild > leftChild)
        ) {
          swap = rightChildIndex;
        }
      }

      if (swap === null) break;

      this.heap[index] = this.heap[swap];
      this.heap[swap] = element;
      index = swap;
    }
  }
}
var halveArray = function (nums) {
  const maxHeap = new MaxHeap();
  let total = 0;
  for (const num of nums) {
    maxHeap.insert(num);
    total += num;
  }
  let target = total / 2;
  let sum=0;
  let ans=0;
  while(target>sum){
    let num=maxHeap.extractMax()/2
    sum+=num;
    maxHeap.insert(num);
    ans++
  }
  return ans
};

李恒道

https://leetcode.cn/problems/minimum-operations-to-exceed-threshold-value-ii/submissions/592983699/
最小堆问题

class MinHeap {
  constructor() {
    this.heap = [];
  }

  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  getLeftChildIndex(index) {
    return 2 * index + 1;
  }

  getRightChildIndex(index) {
    return 2 * index + 2;
  }

  swap(index1, index2) {
    const temp=this.heap[index1]
    this.heap[index1]=this.heap[index2]
    this.heap[index2]=temp
  }

  insert(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0 && this.heap[index] < this.heap[this.getParentIndex(index)]) {
      this.swap(index, this.getParentIndex(index));
      index = this.getParentIndex(index);
    }
  }

  extractMin() {
    if (this.heap.length === 0) {
      return null;
    }
    if (this.heap.length === 1) {
      return this.heap.pop();
    }
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown();
    return min;
  }

  heapifyDown() {
    let index = 0;
    while (this.getLeftChildIndex(index) < this.heap.length) {
      let smallerChildIndex = this.getLeftChildIndex(index);
      if (this.getRightChildIndex(index) < this.heap.length && this.heap[this.getRightChildIndex(index)] < this.heap[smallerChildIndex]) {
        smallerChildIndex = this.getRightChildIndex(index);
      }
      if (this.heap[index] < this.heap[smallerChildIndex]) {
        break;
      }
      this.swap(index, smallerChildIndex);
      index = smallerChildIndex;
    }
  }
}

// Example usage:

/**
 * @param {number[]} nums
 * @param {number} k
 * @Return {number}
 */
var minOperations = function(nums, k) {
  const minHeap = new MinHeap();
  for (const num of nums) {
    minHeap.insert(num)
  }
  let ans=0
  while(true){
    const num1=minHeap.extractMin()
    const num2=minHeap.extractMin()
    if((num1>=k&&num2>=k)||(num1>=k&&num2==undefined)){
      break
    }
    ans++;
    minHeap.insert(Math.min(num1,num2)*2+Math.max(num1,num2))
  }
  return ans;
};

李恒道

https://leetcode.cn/problems/minimum-operations-to-exceed-threshold-value-i/description/
打卡题
简单

var minOperations = function(nums, k) {
    let ans=0;
    for (const num of nums) {
      if(num<k){
        ans++
      }
    }
    return ans
};

李恒道

https://leetcode.cn/problems/missing-number/submissions/593013687/
缺失数字，简单题

var missingNumber = function(nums) {
  const sum = nums.reduce((accumulator, currentValue) => accumulator + currentValue, 0);
  const target = (nums.length * (nums.length + 1)) / 2;
  return target-sum
};