手写算法: 单线程 CPU

1834. 单线程 CPU

思路

1. 分析题意：tasks 是个二维数组，[[enqueueTime, processingTime], ...]表示的是任务的入队时间与执行任务所要耗费的时长。因为现在是个单线程的 CPU，那么同一时间只能执行一项任务。

2. 那么，需要有记录时间的变量（time），记录执行任务队列的变量(queue)。

3. 遍历二维数组，将任务按照入队时间的降序排列，但是遍历后原二维数组的任务编号会丢失，所以在排序前，先添加上任务编号。(task = {index, start, time})

4. 判断当前队列是否有可执行的任务：

• 如果没有，说明还没有达到下一个任务的入队时间，那么直接将时间快进到下一个任务的入队时间

• 如果有，从队列中取出任务执行，因为是单线程，所以在执行的过程中不会执行其他任务。最后，将 当前时间 加上 执行任务所耗费的时间 等于 最新的时间 (time += task.time)

实现过程中用了环境内置的优先队列MinPriorityQueue，具体 Api，可以看 datastructures-js/priority-queue

/**
 * @param {number[][]} tasks
 * @return {number[]}
 */
var getOrder = function(tasks) {
  // 创建最小堆优先队列
  let queue = new MinPriorityQueue();
  // 遍历二维数组，加上任务编号、入队时间、执行任务需要耗费的时长
  tasks = tasks.map((task, index) => ({
    index,
    start: task[0],
    time: task[1],
  }));
  // 将任务按照入队时间降序排列
  tasks.sort((a, b) => b.start - a.start);

  let result = [];
  // 初始化时间
  let time = 0;

  // 当可执行任务长度大于0 或者 队列不为空时
  while (tasks.length > 0 || !queue.isEmpty()) {
    // 当队列为空，并且还没到下一个任务的入队时间，那么直接快进到下一个任务的入队时间
    if (queue.isEmpty() && tasks[tasks.length - 1].start > time) {
      time = tasks[tasks.length - 1].start;
    }

    // 向队列添加可执行任务
    while (tasks.length > 0) {
      // 当下一个任务入队时间大于当前时间，直接中断循环
      if (tasks[tasks.length - 1].start > time) break;

      // 否则，塞入队列
      const task = tasks.pop();
      // 这里的时间乘以100000，我猜是因为n的范围为[1, 100000]，如果不用足够大的值的话，会溢出
      queue.enqueue(task, task.time * 100000 + task.index);
    }

    // 执行任务
    const { element: task } = queue.dequeue();
    // 当前时间 + 执行时间
    time += task.time;
    // 塞入任务的执行顺序
    result.push(task.index);
  }
  return result;
};

手写题: 实现 instanceOf

90. write your own instanceOf

/**
 * @param {any} obj
 * @param {target} target
 * @return {boolean}
 */
function myInstanceOf(obj, target) {
  if (obj === null || typeof obj !== 'object') return false;
  let proto = obj.__proto__;
  const prototype = target.prototype;

  while (proto) {
    if (proto === prototype) return true;
    proto = proto.__proto__;
  }
  return false;
}