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

李恒道

https://leetcode.cn/problems/median-of-two-sorted-arrays/submissions/562723857/?envType=study-plan-v2&envId=top-100-liked
这题是真做不出来
思路太巧妙了
看了答案自己写一遍都感觉骚，边界卡了我一下午

var findMedianSortedArrays = function (nums1, nums2) {
    const getRankK = (nums1, start1, nums2, start2, rank) => {
        const len1 = nums1.length - start1;
        const len2 = nums2.length - start2;
        if (len1 > len2) {
            return getRankK(nums2, start2, nums1, start1, rank)
        }
        if (len1 == 0) {
            return nums2[start2 + rank - 1]
        }
        if (rank == 1) {
            return Math.min(nums1[start1], nums2[start2])
        }
        k = Math.floor(rank / 2)
        k = Math.min(k, len1)
        const num1 = nums1[start1 + k - 1];
        const num2 = nums2[start2 + k - 1];
        if (num1 > num2) {
            return getRankK(nums1, start1, nums2, start2 + k, rank - k)
        } else {
            return getRankK(nums1, start1 + k, nums2, start2, rank - k)
        }
    }
    const len = nums1.length + nums2.length
    const floor = Math.floor(len / 2)
    if (len % 2 == 0) {
        return (getRankK(nums1, 0, nums2, 0, floor) + getRankK(nums1, 0, nums2, 0, floor + 1)) / 2
    } else {
        return getRankK(nums1, 0, nums2, 0, floor + 1)
    }

};

李恒道

https://leetcode.cn/problems/decode-string/submissions/562738091/?envType=study-plan-v2&envId=top-100-liked
堆栈题，秒

var decodeString = function (s) {
    s = s.split("")
    const stack = []
    const handleCycle = () => {
        let str = ""
        let char = stack.pop()
        do {
            str = char+str
            char = stack.pop()
        } while (char !== '[');
        let cycleNum = ""
        while (stack.length !== 0) {
            const code = stack[stack.length - 1].charCodeAt()
            if (code >= 48 && code <= 57) {
                cycleNum = stack.pop() + cycleNum
            } else {
                break;
            }
        }
        cycleNum = parseInt(cycleNum)
        let result = ''
        for (let index = 0; index < cycleNum; index++) {
            result += str
        }
        stack.push(result)
    }
    for (const char of s) {

        if (char === ']') {
            handleCycle()
        } else {
            stack.push(char)
        }
    }
    return stack.join("")
};

李恒道

https://leetcode.cn/problems/largest-rectangle-in-histogram/submissions/562851106/?envType=study-plan-v2&envId=top-100-liked
这题基本看不懂
没理解定理的问题
一个最大的矩形一定是某一高度的矩形
同时边界卡在最后低于该高度的柱
实际上理解了光是扣边界就花了一晚上...

var largestRectangleArea = function (heights) {
    const stack = []
    let maxArea = Number.MIN_SAFE_INTEGER
    heights.unshift(0)
    heights.push(0)
    for (let index = 0; index < heights.length; index++) {
        const height = heights[index];
        while (stack.length != 0) {
            const lastHeight = heights[stack[stack.length - 1]]
            if (lastHeight <= height) {
                break;
            }
            if (stack.length - 2 < 0) {
                //边界
                maxArea = Math.max(maxArea, lastHeight * (index))
                stack.pop()
            } else {
                const leftHeight = heights[stack[stack.length - 2]]
                if (leftHeight < lastHeight) {
                    maxArea = Math.max(maxArea, lastHeight * (index - 1 - stack[stack.length - 2]))
                    stack.pop()
                } else if (leftHeight == lastHeight) {
                    stack.pop()
                } else {
                    break;
                }
            }
        }
        // if(stack.length!==0&&heights[stack[stack.length-1]]===height){
        //     continue;
        // }
        stack.push(index)
    }
    for (let index = stack.length - 1; index >= 0; index--) {
        const heightIdx = stack[index];
        let leftIndex = stack[index - 1] ?? -1
        if (heights[heightIdx] == heights[leftIndex]) {
            continue;
        }
        const height = heights[heightIdx];
        maxArea = Math.max(maxArea, height * (heights.length - leftIndex - 1))
    }
    return maxArea
};

李恒道

https://leetcode.cn/problems/kth-largest-element-in-an-array/?envType=study-plan-v2&envId=top-100-liked
大小堆秒了

class MaxHeadp {
    heap
    border
    constructor(nums) {
        this.heap = nums;
        this.border = nums.length - 1
        this.initHeap();
    }
    initHeap() {
        const endIndex = this.getTopNode(this.border)
        for (let index = endIndex; index >= 0; index--) {
            this.downNode(index)
        }
    }
    haveNum() {
        return this.border + 1
    }
    pop() {
        if (this.border === -1) {
            return undefined
        }
        const temp = this.heap[0];
        this.heap[0] = this.heap[this.border];
        this.border--;
        this.downNode(0)
        return temp
    }
    swap(x, y) {
        let temp = this.heap[x]
        this.heap[x] = this.heap[y]
        this.heap[y] = temp
    }
    downNode(index) {
        let left = this.getLeftNode(index);
        let right = this.getRightNode(index);
        while (left <= this.border || right <= this.border) {
            let maxIndex = undefined
            if (left <= this.border || right <= this.border) {
                maxIndex = this.heap[left] < this.heap[right] ? right : left
            } else {
                maxIndex = left <= this.border ? right : left
            }
            if (this.heap[index] < this.heap[maxIndex]) {
                this.swap(index, maxIndex)
                index = maxIndex
                left = this.getLeftNode(index);
                right = this.getRightNode(index);
            } else {
                break;
            }
        }
    }
    getTopNode(index) {
        return Math.floor((index - 1) / 2)
    }
    getLeftNode(index) {
        return (index + 1) * 2 - 1
    }
    getRightNode(index) {
        return (index + 1) * 2
    }
}

var findKthLargest = function (nums, k) {
    const heap = new MaxHeadp(nums)
    let times = 0
    let lastNum = undefined
    while (heap.haveNum() != 0) {
        const num = heap.pop()
        if (num !== lastNum) {
            times++
        }
        if (times == k) {
            return num
        }
    }
    return -1
};

李恒道

https://leetcode.cn/problems/top-k-frequent-elements/?envType=study-plan-v2&envId=top-100-liked
复杂度N，改进大小堆秒了。..

class MaxHeadp {
    heap
    border
    compare
    constructor(nums, compare) {
        this.heap = nums;
        this.border = nums.length - 1
        this.compare = compare ?? ((a, b) => a < b)
        this.initHeap();
    }
    initHeap() {
        const endIndex = this.getTopNode(this.border)
        for (let index = endIndex; index >= 0; index--) {
            this.downNode(index)
        }
    }
    haveNum() {
        return this.border + 1
    }
    pop() {
        if (this.border === -1) {
            return undefined
        }
        const temp = this.heap[0];
        this.heap[0] = this.heap[this.border];
        this.border--;
        this.downNode(0)
        return temp
    }
    insert() {

    }
    swap(x, y) {
        let temp = this.heap[x]
        this.heap[x] = this.heap[y]
        this.heap[y] = temp
    }
    downNode(index) {
        let left = this.getLeftNode(index);
        let right = this.getRightNode(index);
        while (left <= this.border || right <= this.border) {
            let maxIndex = undefined
            if (left <= this.border || right <= this.border) {
                maxIndex = this.compare(this.heap[left], this.heap[right]) ? right : left;
            } else {
                maxIndex = left <= this.border ? right : left
            }
            // if (this.heap[index] < this.heap[maxIndex]) {
            if (this.compare(this.heap[index], this.heap[maxIndex])) {
                this.swap(index, maxIndex)
                index = maxIndex
                left = this.getLeftNode(index);
                right = this.getRightNode(index);
            } else {
                break;
            }
        }
    }
    getTopNode(index) {
        return Math.floor((index - 1) / 2)
    }
    getLeftNode(index) {
        return (index + 1) * 2 - 1
    }
    getRightNode(index) {
        return (index + 1) * 2
    }
}

var topKFrequent = function (nums, k) {
    const map = new Map()
    const newNums=[]
    for (const num of nums) {
        if (map.has(num)) {
            map.set(num, map.get(num) + 1)
        } else {
            map.set(num, 1)
            newNums.push(num)
        }
    }
    const heap = new MaxHeadp(newNums,(a,b)=>{
        return map.get(a)<map.get(b)
    })
    let times = 0
    let lastNum = undefined
    const result = []
    while (heap.haveNum() != 0) {
        const num = heap.pop()
        if (num !== lastNum) {
            times++
            result.push(num)
        }
        if (times == k) {
            return result
        }
        lastNum=num
    }
    return result
};

李恒道

https://leetcode.cn/problems/find-median-from-data-stream/submissions/563588959/?envType=study-plan-v2&envId=top-100-liked
维护一个大根堆一个小根堆
剩下就是凑边界了
因为总是上的模板有点长

class MaxHeadp {
  heap;
  border;
  compare;
  constructor(nums, compare) {
    this.heap = nums;
    this.border = nums.length - 1;
    this.compare = compare ?? ((a, b) => a < b);
    this.initHeap();
  }
  initHeap() {
    const endIndex = this.getTopNode(this.border);
    for (let index = endIndex; index >= 0; index--) {
      this.downNode(index);
    }
  }
  haveNum() {
    return this.border + 1;
  }
  pop() {
    if (this.border === -1) {
      return undefined;
    }
    const temp = this.heap[0];
    this.heap[0] = this.heap[this.border];
    this.border--;
    this.downNode(0);
    return temp;
  }
  peek() {
    if (this.border === -1) {
      return undefined;
    }
    return this.heap[0];
  }
  insert(num) {
    this.border++;
    if(this.border==this.heap.length){
      this.heap.push(num);
    }else{
      this.heap[this.border]=num
    }
    this.upNode(this.border);
  }
  swap(x, y) {
    let temp = this.heap[x];
    this.heap[x] = this.heap[y];
    this.heap[y] = temp;
  }
  upNode(index) {
    let top = this.getTopNode(index);
    while (top !== -1 && this.compare(this.heap[top], this.heap[index])) {
      this.swap(index, top);
      index = top;
      top = this.getTopNode(index);
    }
  }
  downNode(index) {
    let left = this.getLeftNode(index);
    let right = this.getRightNode(index);
    while (left <= this.border || right <= this.border) {
      let maxIndex = undefined;
      if (left <= this.border || right <= this.border) {
        maxIndex = this.compare(this.heap[left], this.heap[right])
          ? right
          : left;
      } else {
        maxIndex = left <= this.border ? right : left;
      }
      // if (this.heap[index] < this.heap[maxIndex]) {
      if (this.compare(this.heap[index], this.heap[maxIndex])) {
        this.swap(index, maxIndex);
        index = maxIndex;
        left = this.getLeftNode(index);
        right = this.getRightNode(index);
      } else {
        break;
      }
    }
  }
  getTopNode(index) {
    return Math.floor((index - 1) / 2);
  }
  getLeftNode(index) {
    return (index + 1) * 2 - 1;
  }
  getRightNode(index) {
    return (index + 1) * 2;
  }
}

var MedianFinder = function () {
  this.leftHeap = new MaxHeadp([]);
  this.rightHeap = new MaxHeadp([], (a, b) => a > b);
  // this.rightHeap.insert(-2)
  // this.rightHeap.insert(-1)
  // this.rightHeap.insert(-3)
};

/**
 * @param {number} num
 * @Return {void}
 */
MedianFinder.prototype.addNum = function (num) {
  const center=this.findMedian()
  if(num<center){
    this.leftHeap.insert(num);
  }else{
    this.rightHeap.insert(num);
  }

  if (this.leftHeap.border - 1 > this.rightHeap.border) {
    this.rightHeap.insert(this.leftHeap.pop());
  }
  if (this.rightHeap.border - 1 > this.leftHeap.border) {
    this.leftHeap.insert(this.rightHeap.pop());
  }
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function () {
  const nums=this.leftHeap.border + this.rightHeap.border + 2
  const isOne =
    (nums) % 2 === 0 ? false : true;
  if (isOne) {
    return Math.floor(nums/2)<=this.leftHeap.border? this.leftHeap.peek():this.rightHeap.peek();
  } else {
    return ((this.leftHeap.peek() + this.rightHeap.peek()) / 2);
  }
};

李恒道

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/submissions/563593218/?envType=study-plan-v2&envId=top-100-liked
前缀和秒的

var maxProfit = function (prices) {
  const min = [];
  let lastMin = Number.MAX_SAFE_INTEGER;
  for (let index = 0; index < prices.length; index++) {
    const price = prices[index];
    min.push(lastMin);
    lastMin = Math.min(lastMin, price);
  }
  let maxProfit = 0;
  for (let index = 1; index < prices.length; index++) {
    const price = prices[index];
    maxProfit=Math.max(maxProfit,price-min[index])
  }
  return maxProfit;
};

李恒道

https://leetcode.cn/problems/jump-game/submissions/563613612/?envType=study-plan-v2&envId=top-100-liked
递归秒的
方法应该是有问题了
擦边过的

var canJump = function (nums) {
  let status = false;
  const jump = (pos) => {
    if (pos == nums.length - 1) {
      status = true;
      return;
    }
    if (pos > nums.length - 1) {
      return;
    }
    const times = Math.min(nums[pos], nums.length - 1);
    for (let index = 1;!status&& index <= times; index++) {
      !status&&jump(pos + index);
    }
    nums[pos] = 0;
  };
  jump(0);
  return status;
};

李恒道

https://leetcode.cn/problems/jump-game-ii/submissions/563760469/?envType=study-plan-v2&envId=top-100-liked
会上一题的贪心思路了
靠变量缓存上一步秒了

var jump = function (nums) {
    if(nums.length==1){
        return 0
    }

    let times = 1;
    let lastMax = 0
    let maxLength = nums[0];
    while (maxLength < (nums.length - 1)) {
        let newMax = maxLength;
        times++;
        for (let index = lastMax; index <= maxLength; index++) {
            const num = nums[index];
            newMax = Math.max(newMax, index + num)
        }
        if(newMax===maxLength){
            return -1
        }

        lastMax = maxLength;
        maxLength = newMax;
    }
    return times;

};

李恒道

https://leetcode.cn/problems/longest-palindromic-substring/submissions/563817622/
dp秒的
但是复杂度很差

var longestPalindrome = function (s) {
    s = s.split("");
    let l = 0, r = 0;
    const arr = new Array(s.length)
    for (let index = 0; index < arr.length; index++) {
        arr[index] = new Array(s.length).fill(false);
    }
    arr[0][0] = true;
    for (let index = 1; index < s.length; index++) {
        arr[index][index] = true;
        arr[index - 1][index] = s[index - 1] === s[index];
        if (arr[index - 1][index]) {
            l = index - 1;
            r = index
        }
    }

    for (let index = s.length - 3; index >= 0; index--) {
        for (let indey = index + 2; indey < s.length; indey++) {
            if (s[index] === s[indey]) {
                arr[index][indey] = arr[index + 1][indey - 1]
                if (arr[index][indey]&&(indey - index) > (r - l)) {
                    l = index;
                    r = indey
                }
            }
        }
    }
    return s.slice(l,r+1).join("")
};