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

李恒道

https://leetcode.cn/problems/merge-k-sorted-lists/?envType=study-plan-v2&envId=top-100-liked
理论可以用小根堆建堆的
懒得优化了

var mergeKLists = function (lists) {
    let newNode = {
        next: null
    }
    const ret = newNode
    while (lists.length != 0) {
        if(lists[0]==null){
            lists.splice(0,1)
            continue
        }
        let maxChain = 0
        for (let index = 1; index < lists.length; index++) {
            const chain = lists[index];
            if(chain==null){
                continue;
            }
            if (chain.val <= lists[maxChain].val) {
                maxChain = index
            }
        }
        newNode.next = lists[maxChain]
        newNode = newNode.next
        lists[maxChain] = lists[maxChain].next
        if (lists[maxChain] == null) {
            lists.splice(maxChain,1)
        }
    }
    return ret.next
};

李恒道

LRU问题
https://leetcode.cn/problems/lru-cache/?envType=study-plan-v2&envId=top-100-liked
打败98%~

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.num = 0;
  this.map = new Map();
  this.chain = null;
  this.tail = null;
};
LRUCache.prototype.appendHead = function (node) {
  if (this.tail == node) {
    if (node.last == null) {
      return;
    }
    this.tail = this.tail.last;
  }
  if (node.last) {
    node.last.next = node.next;
  }
  if (node.next&&node.last) {
    node.next.last = node.last;
  }
  if (node != this.chain) {
    node.next = this.chain;
    this.chain.last = node;
    node.last = null;
    this.chain = node;
  }
};
/**
 * @param {number} key
 * @Return {number}
 */
LRUCache.prototype.get = function (key) {
  const node = this.map.get(key);
  if (node == null) {
    return -1;
  }
  this.appendHead(node);
  return node.val;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  const data = this.map.get(key);
  if (data == undefined) {
    this.num++;
    this.chain = {
      last: null,
      next: this.chain,
      val: value,
      key,
    };
    if (this.chain.next) {
      this.chain.next.last = this.chain;
    }
    if (this.tail == null) {
      this.tail = this.chain;
    }
    this.map.set(key, this.chain);
    if (this.num > this.capacity) {
      this.map.delete(this.tail.key);
      this.tail = this.tail.last;
      if (this.tail?.next) {
        this.tail.next = null;
      }
      this.num--;
    }
  } else {
    data.val = value;
    this.appendHead(data);
  }
};

李恒道

https://leetcode.cn/problems/maximum-depth-of-binary-tree/submissions/560910551/?envType=study-plan-v2&envId=top-100-liked
深度题
秒

var maxDepth = function (root) {
  if(root==null){
    return 0
  }
  const leftDeep = maxDepth(root.left);
  const rightDeep = maxDepth(root.right);
  return Math.max(leftDeep, rightDeep) + 1;
};

李恒道

https://leetcode.cn/problems/invert-binary-tree/submissions/560910572/?envType=study-plan-v2&envId=top-100-liked
翻转问题
秒

var invertTree = function (root) {
  if(root==null){
    return null
  }
  const left=invertTree(root.left)
  const right=invertTree(root.right)
  root.left=right;
  root.right=left
  return root
};

李恒道

对称题
https://leetcode.cn/problems/symmetric-tree/submissions/560910631/?envType=study-plan-v2&envId=top-100-liked
秒

const check = (left, right) => {
  if (left == null || right == null) {
    return left === right;
  }
  if (left.val == right.val) {
    return check(left.left, right.right) && check(left.right, right.left);
  } else {
    return false;
  }
};
var isSymmetric = function (root) {
  return check(root.left, root.right);
};

李恒道

https://leetcode.cn/problems/diameter-of-binary-tree/submissions/560910726/?envType=study-plan-v2&envId=top-100-liked
直径题，秒

var diameterOfBinaryTree = function (root) {
  let max = 0;
  const getMax = (node) => {
    if (node === null) {
      return 0;
    }
    const left = getMax(node.left);
    const right = getMax(node.right);
    max = Math.max(max, left + right);
    return Math.max(left, right) + 1;
  };
  getMax(root);
  return max;
};

李恒道

https://leetcode.cn/problems/binary-tree-level-order-traversal/submissions/560910947/?envType=study-plan-v2&envId=top-100-liked
层序问题，秒
睡觉~

var levelOrder = function (root) {
  const ret = [];
  let stack = [root];
  do {
    const nextStack = [];
    const num = [];
    for (let index = 0; index < stack.length; index++) {
      const node = stack[index];
      if(node==null){
        continue;
      }
      num.push(node.val);
      nextStack.push(node.left, node.right);
    }
    if(num.length!=0){
      ret.push(num);
    }
    stack=nextStack
  } while (stack.length!=0);
  return ret;
};

李恒道

数组转二叉树
https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/submissions/560911148/?envType=study-plan-v2&envId=top-100-liked

95%执行率秒了

var sortedArrayToBST = function (nums) {
  const buildTree = (left, right) => {
    if (left + 1 == right) {
      const leftNode = {
        left: null,
        right: null,
        val: nums[left],
      };
      const rightNode = {
        left: null,
        right: null,
        val: nums[right],
      };
      rightNode.left = leftNode;
      return rightNode;
    }else if(left==right){
      return {
        left:null,
        right:null,
        val:nums[left]
      }
    }
    const center = left+Math.floor((right - left) / 2);
    left = buildTree(left, center - 1);
    right = buildTree(center + 1, right);
    return {
      right,
      left,
      val: nums[center],
    };
  };
  return buildTree(0, nums.length - 1);
};

李恒道

https://leetcode.cn/problems/validate-binary-search-tree/submissions/561308458/?envType=study-plan-v2&envId=top-100-liked
中序题
一开始思路错了

var isValidBST = function (root) {
  let lastValue = Number.MIN_SAFE_INTEGER;
  let status = true;
  const checkNode = (root) => {
    if(root==null){
      return 
    }
    checkNode(root.left);
    if (root.val <= lastValue) {
      status = false;
      return;
    }else{
      lastValue=root.val
    }
    checkNode(root.right);
  };
  checkNode(root)
  return status;
};

李恒道

https://leetcode.cn/problems/kth-smallest-element-in-a-bst/submissions/561308503/?envType=study-plan-v2&envId=top-100-liked
缝缝补补又是一道

var kthSmallest = function (root, k) {
  let index = 0;
  let ret = undefined;
  const checkNode = (root) => {
    if (root == null || ret !== undefined) {
      return;
    }
    checkNode(root.left);
    index++;
    if (k == index) {
      ret = root.val;
    }
    checkNode(root.right);
  };
  checkNode(root);
  return ret;
};