高频手写 JS（二） #

var reverseList = function (head) {
  let prev = null,
    curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
};

/**
 * @param {number} capacity
 */
var Solution = function (capacity) {
  this.cache = new Map();
  this.capacity = capacity;
};

/**
 * @param {number} key
 * @return {number}
 */
Solution.prototype.get = function (key) {
  if (!this.cache.has(key)) return -1;
  const value = this.cache.get(key);
  // 确保它是最新的
  this.cache.delete(key);
  this.cache.set(key, value);
  return value;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
Solution.prototype.set = function (key, value) {
  // 如果存在则删除
  if (this.cache.has(key)) this.cache.delete(key);

  // 将其存储在缓存中
  this.cache.set(key, value);

  // 将其存储在缓存中后，请确保不要超出最大范围
  if (this.cache.size > this.capacity) {
    const first = this.cache.keys().next().value;
    this.cache.delete(first);
  }
};

module.exports = {
  Solution: Solution,
};

function threeOrders(root) {
  const pre = (cur, arr = []) => {
    if (!cur) return arr;
    arr.push(cur.val);
    pre(cur.left, arr);
    pre(cur.right, arr);
    return arr;
  };
  const mid = (cur, arr = []) => {
    if (!cur) return arr;
    mid(cur.left, arr);
    arr.push(cur.val);
    mid(cur.right, arr);
    return arr;
  };
  const next = (cur, arr = []) => {
    if (!cur) return arr;
    next(cur.left, arr);
    next(cur.right, arr);
    arr.push(cur.val);
    return arr;
  };
  return [pre(root), mid(root), next(root)];
}

function GetLeastNumbers_Solution(input, k) {
  if (k === 0) return [];
  let arr = input.slice(0, k);
  for (let i = k; i < input.length; i++) {
    let max = 0;
    for (let j in arr) {
      max = arr[j] > arr[max] ? j : max;
    }
    arr[max] = arr[max] > input[i] ? input[i] : arr[max];
  }
  return arr;
}

function levelOrder(root) {
  function preOrder(root, level) {
    if (root == null) return;
    if (level >= res.length) res.push([]);
    res[level].push(root.val);
    preOrder(root.left, level + 1);
    preOrder(root.right, level + 1);
  }
  let res = [];
  preOrder(root, 0);
  return res;
}

function findKth(a, n, K) {
  function quickSort(arr) {
    if (arr.length <= 1) return arr;
    const pivotIndex = Math.floor(arr.length / 2);
    const pivot = arr.splice(pivotIndex, 1)[0];
    const left = [];
    const right = [];
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] < pivot) {
        left.push(arr[i]);
      } else {
        right.push(arr[i]);
      }
    }
    return quickSort(left).concat([pivot], quickSort(right));
  }
  const arr = quickSort(a);
  return arr[n - K];
}

function addStrings(num1, num2) {
  let i = num1.length - 1,
    j = num2.length - 1,
    add = 0;
  const ans = [];
  while (i >= 0 || j >= 0 || add != 0) {
    // charAt 字符串中的字符从左向右索引
    const x = Number(num1.charAt(i));
    const y = Number(num2.charAt(j));
    const result = x + y + add;
    ans.push(result % 10);
    add = Math.floor(result / 10);
    i = i - 1;
    j = j - 1;
  }
  // reverse() 方法将数组中元素的位置颠倒
  return ans.reverse().join("");
}

/**
 * 解法二：递归
 * 思路：
 * （1）每次比较两个链表当前结点的值，然后取较小值的链表指针往后，另一个不变送入递归中。
 * （2）递归回来的结果我们要加在当前较小值的结点后面，相当于不断在较小值后面添加结点。
 * （3）递归的终止是两个链表为空。
 * 时间复杂度: O(n)，最坏相当于遍历两个链表每个结点一次
 * 空间复杂度: O(n), 递归栈长度最大为 n
 */
function Merge(pHead1, pHead2) {
  if (!pHead1) return pHead2;
  if (!pHead2) return pHead1;
  if (pHead1.val <= pHead2.val) {
    pHead1.next = Merge(pHead1.next, pHead2);
    return pHead1;
  } else {
    pHead2.next = Merge(pHead2.next, pHead1);
    return pHead2;
  }
}

var stack1 = [];
var stack2 = [];

function push(node) {
  // 入栈时stack1存入元素
  stack1.push(node);
}

function pop() {
  // 如果stack2没有元素，则将stack1中元素pop出再push存入stack2
  if (!stack2.length) {
    while (stack1.length) {
      stack2.push(stack1.pop());
    }
  }
  // stack2弹出元素
  return stack2.pop();
}