题目

460. LFU 缓存

details

class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.freq = 1;
        this.prev = null;
        this.next = null;
    }
}

class DoublyLinkedList {
    constructor() {
        this.head = new Node(null, null);
        this.tail = new Node(null, null);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    addNode(node) {
        let realTail = this.tail.prev;
        realTail.next = node;
        node.prev = realTail;
        node.next = this.tail;
        this.tail.prev = node;
    }

    removeNode(node) {
        let prev = node.prev;
        let next = node.next;
        prev.next = next;
        next.prev = prev;
    }

    isEmpty() {
        return this.head.next === this.tail;
    }
}

class LFUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.minFreq = 0;
        this.cache = new Map();
        this.freqMap = new Map();
    }

    get(key) {
        if (!this.cache.has(key)) {
            return -1;
        }
        let node = this.cache.get(key);
        this._update(node);
        return node.value;
    }

    put(key, value) {
        if (this.capacity === 0) return;

        if (this.cache.has(key)) {
            let node = this.cache.get(key);
            node.value = value;
            this._update(node);
        } else {
            if (this.size >= this.capacity) {
                let minFreqList = this.freqMap.get(this.minFreq);
                let nodeToRemove = minFreqList.head.next;
                this.cache.delete(nodeToRemove.key);
                minFreqList.removeNode(nodeToRemove);
                this.size--;
            }
            let newNode = new Node(key, value);
            this.cache.set(key, newNode);
            if (!this.freqMap.has(1)) {
                this.freqMap.set(1, new DoublyLinkedList());
            }
            this.freqMap.get(1).addNode(newNode);
            this.minFreq = 1;
            this.size++;
        }
    }

    _update(node) {
        let freq = node.freq;
        let list = this.freqMap.get(freq);
        list.removeNode(node);
        if (freq === this.minFreq && list.isEmpty()) {
            this.minFreq++;
        }
        node.freq++;
        if (!this.freqMap.has(node.freq)) {
            this.freqMap.set(node.freq, new DoublyLinkedList());
        }
        this.freqMap.get(node.freq).addNode(node);
    }
}

98. 验证二叉搜索树

details

/*
 * 98. 验证二叉搜索树
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */

// 中序遍历的时候能拿到有序的 ，判断到不是 递增的时候 return  false
var isValidBST = function (root) {
    let preMax = -Infinity;

    let ans = true;
    traverse(root);
    return ans;

    function traverse(root) {
        if (!root) return;
        traverse(root.left);
        console.log(root.val);
        if (root.val > preMax) {
            preMax = root.val;
        } else {
            // 不是递增的，
            ans = false;
            return;
        }
        traverse(root.right);
    }
};

// 判断 左子树小于 根节点，柚子树 大于根节点
var isValidBST = function (root) {
    return traverse(root, null, null);
    function traverse(root, min, max) {
        if (!root) return true;
        if (min != null && root.val <= min.val) return false;
        if (max != null && root.val >= max.val) return false;

        return traverse(root.left, min, root) && traverse(root.right, root, max);
    }
};

146. LRU 缓存

details

class ListNode {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

class LRUCache {

constructor(capacity) {
this.capacity = capacity;
this.map = new Map();
this.head = new ListNode(null, null);
this.tail = new ListNode(null, null);
this.head.next = this.tail;
this.tail.prev = this.head;
}

    _remove(node) {
        let prev = node.prev;
        let next = node.next;
        prev.next = next;
        next.prev = prev;
    }

    _add(node) {
        let realTail = this.tail.prev;
        realTail.next = node;
        node.prev = realTail;
        node.next = this.tail;
        this.tail.prev = node;
    }

    get(key) {
        if (this.map.has(key)) {
            let node = this.map.get(key);
            this._remove(node);
            this._add(node);
            return node.value;
        } else {
            return -1;
        }
    }

    put(key, value) {
        if (this.map.has(key)) {
            this._remove(this.map.get(key));
        }

        let newNode = new ListNode(key, value);
        this._add(newNode);
        this.map.set(key, newNode);

        if (this.map.size > this.capacity) {
            let firstNode = this.head.next;
            this._remove(firstNode);
            this.map.delete(firstNode.key);
        }
    }

}

剑指 Offer II 044. 二叉树每层的最大值

details

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 剑指 Offer II 044. 二叉树每层的最大值
 * @param {TreeNode} root
 * @return {number[]}
 */
var largestValues = function(root) {
  //
  const ans = [];
  if (!root) {
    return ans;
  }
  //
  const queue = [root];
  while (queue.length) {
    const len = queue.length;
    let i = 0;
    let levelMax = -Number.MAX_SAFE_INTEGER;
    while (i < len) {
      i++;
      const item = queue.shift();
      if (!item) {
        continue;
      }
      levelMax = Math.max(item.val, levelMax);
      //
      item.left && queue.push(item.left);
      item.right && queue.push(item.right);
    }
    levelMax !== -Number.MAX_SAFE_INTEGER && ans.push(levelMax);
  }

  return ans;
};

102. 二叉树的层序遍历

details

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 102. 二叉树的层序遍历
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
    if (root === null) return [];

    let result = [];
    const queue = [root];
    while (queue.length) {
        let level = [];
        const len = queue.length;
        for (let i = 0; i < len; i++) {
            const item = queue.shift();
            level.push(item.val);
            if (item.left) queue.push(item.left);
            if (item.right) queue.push(item.right);
        }
        result.push(level);
    }
    return result;
};

剑指 Offer II 044. 二叉树每层的最大值

details

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 剑指 Offer II 044. 二叉树每层的最大值
 * @param {TreeNode} root
 * @return {number[]}
 */
var largestValues = function(root) {
  //
  const ans = [];
  if (!root) {
    return ans;
  }
  //
  const queue = [root];
  while (queue.length) {
    const len = queue.length;
    let i = 0;
    let levelMax = -Number.MAX_SAFE_INTEGER;
    while (i < len) {
      i++;
      const item = queue.shift();
      if (!item) {
        continue;
      }
      levelMax = Math.max(item.val, levelMax);
      //
      item.left && queue.push(item.left);
      item.right && queue.push(item.right);
    }
    levelMax !== -Number.MAX_SAFE_INTEGER && ans.push(levelMax);
  }

return ans;
};

104. 二叉树的最大深度

details

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 104. 二叉树的最大深度
 * @param {TreeNode} root
 * @return {number}
 */

var maxDepth = function(root) {
    let depth = 0
    let ans = 0
    traverse(root);
    return ans;

    function traverse(root) {
        if(!root) {
            ans = Math.max(ans,depth)
            return
        }
        depth++
        traverse(root.left)
        traverse(root.right)
        depth--
    }
};
// console.log(ans)


/**
 * 通过子树高度推导
*/
var maxDepth = function(root) {
  if (!root) return 0;
  const maxLeft = maxDepth(root.left);
  const maxRight = maxDepth(root.right);
  return Math.max(maxLeft, maxRight) + 1;
};

105. 从前序与中序遍历序列构造二叉树

details

/*
 * 105. 从前序与中序遍历序列构造二叉树
 */
/**
 * @param {number[]} preOrder
 * @param {number[]} inOrder
 * @return {TreeNode}
 */
var buildTree = function(preOrder, inOrder) {
  const map = Object.create(null);
  // 遍历一遍 中序遍历结果 得到hash 表，用hash 表查找节点对应的 左子树 跟右子树
  for (let i = 0; i < inOrder.length; i++) {
    map[inOrder[i]] = i;
  }
  const len = preOrder.length - 1;

return traverse(preOrder, inOrder, 0, len, 0, len);

function traverse(preOrder, inOrder, preStart, preEnd, inStart, inEnd) {
if (preStart > preEnd || inStart > inEnd) return null;
// 前序遍历第一个元素就是 根节点
const root = new TreeNode(preOrder[preStart]);
// 找到 root 在中序遍历中的元素
const rootIndex = map[root.val];
const leftSubTreeSize = rootIndex - inStart;
// 递归地构造左子树，并连接到根节点
// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素

    root.left = traverse(preOrder, inOrder, preStart + 1, preStart + leftSubTreeSize, inStart, rootIndex - 1);

    // 递归地构造右子树，并连接到根节点
    // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素

    root.right = traverse(preOrder, inOrder, preStart + leftSubTreeSize + 1, preEnd, rootIndex + 1, inEnd);
    return root;

}
};

// Definition for a binary tree node.
function TreeNode(val, left, right) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}

99. 恢复二叉搜索树

details

/*
 * 99. 恢复二叉搜索树
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function(root) {
  // 恰好有2个节点，找到这2个节点，交换位置即可
  let first = null;
  let second = null;
  let prev = new TreeNode(-Infinity);

  traverse(root);

  // 找到元素了，交换位置
  const temp = first.val;
  first.val = second.val;
  second.val = temp;

  function traverse(root) {
    if (!root) return null;
    traverse(root.left);
    // 中序遍历代码位置，找出那两个节点
    if (root.val < prev.val) {
      // root 不符合有序性
      if (first === null) {
        // 第一个错位节点是 prev
        first = prev;
      }
      // 第二个错位节点是 root
      second = root;
    }
    prev = root;

    traverse(root.right);
  }
};

function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

124. 二叉树中的最大路径和

details

/*
 * 124. 二叉树中的最大路径和
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxPathSum = function(root) {
  let ans = -Number.MAX_SAFE_INTEGER;
  traverse(root);
  return ans;

function traverse(root) {
if (!root) return 0;
const leftMax = Math.max(0, traverse(root.left));
const rightMax = Math.max(0, traverse(root.right));

    // 当前节点路径
    const newPath = leftMax + root.val + rightMax;
    ans = Math.max(ans, newPath);

    // 单边最大贡献
    // 至少包含一个节点 当前节点
    return root.val + Math.max(leftMax, rightMax);

}
};

700. 二叉搜索树中的搜索

details

/*
 * 700. 二叉搜索树中的搜索
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function(root, val) {
  if (!root) return null;
  if (root.val === val) {
    return root;
  } else if (root.val > val) {
    return searchBST(root.left, val);
  } else {
    return searchBST(root.right, val);
  }
};

35. 搜索插入位置

details

/*
 * 35. 搜索插入位置
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

// 问题转换为 查找第一个大于等于 target 的元素
var searchInsert = function(nums, target) {
let left = 0;
let right = nums.length - 1;
// 最大的一个元素，则插入到尾部
let ans = nums.length;
while (left <= right) {
let mid = (left + (right - left) / 2) >> 0;
if (nums[mid] >= target) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
};

701. 二叉搜索树中的插入操作

details

/*
 * 701. 二叉搜索树中的插入操作
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoBST = function(root, val) {
  //
  if (!root) return new TreeNode(val);

  if (root.val < val) {
    root.right = insertIntoBST(root.right, val);
  } else {
    root.left = insertIntoBST(root.left, val);
  }
  return root;
};

function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

450. 删除二叉搜索树中的节点

details

/*
 * 450. 删除二叉搜索树中的节点
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function(root, key) {
  if (!root) return null;
  if (root.val > key) {
    root.left = deleteNode(root.left, key);
  } else if (root.val < key) {
    root.right = deleteNode(root.right, key);
  } else {
    // 单边只有一个节点
    if (root.left === null) return root.right;
    if (root.right === null) return root.left;
    // 找到右子树最小的节点
    const minNode = getLeftMost(root.right);
    root.val = minNode.val;
    root.right = deleteNode(root.right, minNode.val);
  }
  return root;

function getLeftMost(root) {
while (root.left !== null) {
root = root.left;
}
return root;
}
};

297. 二叉树的序列化与反序列化

details

/*
 * 297. 二叉树的序列化与反序列化
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
  const ans = [];
  traverse(root);
  function traverse(root) {
    if (!root) {
      ans.push(null);
      return null;
    }
    ans.push(root.val);
    traverse(root.left);
    traverse(root.right);
  }

  return ans.toString();
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
  const arr = data.split(',');

  return traverse(arr);

  function traverse() {
    if (!arr.length) return null;
    const val = arr.shift();
    if (!val) return null;
    const root = new TreeNode(val);
    root.left = traverse();
    root.right = traverse();
    return root;
  }
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}