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

李恒道

https://leetcode.cn/submissions/detail/588897066/
这个题真的是凹了好久，写的太脏了

class MaxHeap {
    constructor(comparator = (a, b) => a - b) {
        this.heap = [];
        this.comparator = comparator;
    }

    // 获取父节点索引
    parentIndex(index) {
        return Math.floor((index - 1) / 2);
    }

    // 获取左子节点索引
    leftChildIndex(index) {
        return 2 * index + 1;
    }

    // 获取右子节点索引
    rightChildIndex(index) {
        return 2 * index + 2;
    }

    // 交换两个节点
    swap(index1, index2) {
        const temp = this.heap[index2];
        this.heap[index2] = this.heap[index1];
        this.heap[index1] = temp;
    }

    // 向堆中插入元素
    insert(value) {
        this.heap.push(value);
        this.heapifyUp();
    }

    // 堆化上移
    heapifyUp() {
        let index = this.heap.length - 1;
        while (index > 0 && this.comparator(this.heap[index], this.heap[this.parentIndex(index)]) > 0) {
            this.swap(index, this.parentIndex(index));
            index = this.parentIndex(index);
        }
    }

    // 移除堆顶元素
    extractMax() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();
        const max = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown(0);
        return max;
    }

    // 堆化下移
    heapifyDown(index) {
        let largest = index;
        const left = this.leftChildIndex(index);
        const right = this.rightChildIndex(index);

        if (left < this.heap.length && this.comparator(this.heap[left], this.heap[largest]) > 0) {
            largest = left;
        }

        if (right < this.heap.length && this.comparator(this.heap[right], this.heap[largest]) > 0) {
            largest = right;
        }

        if (largest !== index) {
            this.swap(index, largest);
            this.heapifyDown(largest);
        }
    }

    // 获取堆顶元素
    peek() {
        return this.heap.length > 0 ? this.heap[0] : null;
    }

    // 获取堆的大小
    size() {
        return this.heap.length;
    }
}

// 示例使用

var ExamRoom = function (n) {
    this.n = n
    this.seats = {};
    this.left = {};
    this.right = {};
    const getDistance = (l, r) => {
        if (l == -1) {
            return r
        } else if (r == n) {
            return n - l - 1
        } else {
            return Math.floor(((r - l) / 2))
        }
    }
    this.maxHeap = new MaxHeap((a, b) => {
        const d1 = getDistance(a[0], a[1]);
        const d2 = getDistance(b[0], b[1]);
        if (d1 == d2) {
            return b[1] - a[1]
        }
        return d1 - d2
    }); // 默认比较器，构建最大堆
    this.maxHeap.insert([-1, n])
};

/**
 * @Return {number}
 */
ExamRoom.prototype.seat = function () {
    const n = this.n
    const [l, r] = this.maxHeap.extractMax()
    if (l == -1 && !this.seats[0] && (this.seats[r] || r == n)) {
        this.seats[0] = true;
        this.left[0] = -1;
        this.right[0] = r;
        this.left[r] = 0;
        if (r - 1 !== 0) {
            this.maxHeap.insert([0, r])
        }
        return 0
    } else if (r == n && !this.seats[n - 1] && (this.seats[l] || l == -1)) {
        this.seats[n - 1] = true;
        this.left[n - 1] = l;
        this.right[n - 1] = n;
        this.right[l] = n - 1;
        if (n - 1 - 1 != l) {
            this.maxHeap.insert([l, n - 1])
        }
        return n - 1
    } else if (this.seats[l] && this.seats[r]) {
        const center = Math.floor((l + r) / 2)
        if (this.seats[center]) {
            return this.seat()
        }
        this.seats[center] = true;
        this.left[center] = l;
        this.right[center] = r;
        this.right[l] = center;
        this.left[r] = center;
        if (center - 1 != l) {
            this.maxHeap.insert([l, center]);
        }
        if (r - 1 != center) {
            this.maxHeap.insert([center, r]);
        }
        return center
    }
    return this.seat()

};

/** 
 * @param {number} p
 * @return {void}
 */
ExamRoom.prototype.leave = function (p) {
    this.seats[p] = false;
    const l = this.left[p];
    const r = this.right[p];
    if (r !== this.n) {
        this.left[r] = l
    }
    if (l !== -1) {
        this.right[l] = r
    }
    this.maxHeap.insert([this.left[p], this.right[p]]);
};

李恒道

https://leetcode.cn/submissions/detail/588930611/
堆+贪心问题

class MaxHeap {
  constructor(comparator = (a, b) => a - b) {
    this.heap = [];
    this.comparator = comparator;
  }

  // 获取父节点索引
  parentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  // 获取左子节点索引
  leftChildIndex(index) {
    return 2 * index + 1;
  }

  // 获取右子节点索引
  rightChildIndex(index) {
    return 2 * index + 2;
  }

  // 交换两个节点
  swap(index1, index2) {
    const temp = this.heap[index2];
    this.heap[index2] = this.heap[index1];
    this.heap[index1] = temp;
  }

  // 向堆中插入元素
  insert(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

  // 堆化上移
  heapifyUp() {
    let index = this.heap.length - 1;
    while (
      index > 0 &&
      this.comparator(this.heap[index], this.heap[this.parentIndex(index)]) > 0
    ) {
      this.swap(index, this.parentIndex(index));
      index = this.parentIndex(index);
    }
  }

  // 移除堆顶元素
  extractMax() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();
    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown(0);
    return max;
  }

  // 堆化下移
  heapifyDown(index) {
    let largest = index;
    const left = this.leftChildIndex(index);
    const right = this.rightChildIndex(index);

    if (
      left < this.heap.length &&
      this.comparator(this.heap[left], this.heap[largest]) > 0
    ) {
      largest = left;
    }

    if (
      right < this.heap.length &&
      this.comparator(this.heap[right], this.heap[largest]) > 0
    ) {
      largest = right;
    }

    if (largest !== index) {
      this.swap(index, largest);
      this.heapifyDown(largest);
    }
  }

  // 获取堆顶元素
  peek() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }

  // 获取堆的大小
  size() {
    return this.heap.length;
  }
}
/**
 * @param {number[]} apples
 * @param {number[]} days
 * @Return {number}
 */
var eatenApples = function (apples, days) {
  const maxHeap = new MaxHeap((a, b) => {
    return b.day - a.day;
  });
  let nextDay = 0;
  let total = 0;
  for (let index = 0; index < apples.length; index++) {
    maxHeap.insert({ num: apples[index], day: index + days[index] });
    while (maxHeap.size() !== 0) {
      const obj = maxHeap.extractMax();
      if (obj.day > nextDay && obj.num > 0) {
        maxHeap.insert({ num: obj.num - 1, day: obj.day });
        total++;
        break;
      }
    }
    nextDay++;
  }
  while (maxHeap.size() !== 0) {
    const obj = maxHeap.extractMax();
    if (obj.day > nextDay && obj.num > 0) {
      maxHeap.insert({ num: obj.num - 1, day: obj.day });
      total++;
      nextDay++;
    }
  }
  return total;
};

李恒道

https://leetcode.cn/problems/balanced-binary-tree/submissions/588931291/
爽一题收工

var isBalanced = function (root) {
  let ans = true;
  const dfs = (node) => {
    if (node == null) {
      return 0;
    }
    const l = dfs(node.left);
    const r = dfs(node.right);
    if (Math.abs(l - r) > 1) {
      ans = false;
    }
    return Math.max(l, r) + 1;
  };
  dfs(root)
  return ans
};

李恒道

https://leetcode.cn/problems/minimum-cost-for-cutting-cake-i/submissions/589239949/
贪心太难凹了
看了一眼答案用了缓存dp，一次过

var minimumCost = function (m, n, horizontalCut, verticalCut) {
    const cache = new Map()
    const dfs = (x, y, xLen, yLen) => {
        const tag = `${x} ${y} ${xLen} ${yLen}`
        if (cache.has(tag)) {
            return cache.get(tag)
        }
        if (xLen == 1 && yLen == 1) {
            return 0
        }
        let ans = Number.MAX_SAFE_INTEGER;
        for (let index = 1; index < xLen; index++) {
            ans = Math.min(ans, dfs(x, y, index, yLen) + dfs(x + index, y, xLen - index, yLen) + horizontalCut[x + index - 1])
        }
        for (let index = 1; index < yLen; index++) {
            ans = Math.min(ans, dfs(x, y, xLen, index) + dfs(x, y + index, xLen, yLen - index) + verticalCut[y + index - 1])
        }
        cache.set(tag,ans)
        return ans
    }
    return dfs(0, 0, m, n)
};

李恒道

https://leetcode.cn/problems/minimum-cost-for-cutting-cake-ii/submissions/589244396/
贪心好神奇

/**
 * @param {number} m
 * @param {number} n
 * @param {number[]} horizontalCut
 * @param {number[]} verticalCut
 * @Return {number}
 */
var minimumCost = function(m, n, horizontalCut, verticalCut) {
      horizontalCut.sort((a, b) => b - a);
    verticalCut.sort((a, b) => b - a);
    h = 0;
    v = 0;
    vBlock = 1;
    hBlock = 1;
    ans = 0
    while (h < horizontalCut.length && v < verticalCut.length) {
        if (horizontalCut[h] > verticalCut[v]) {
            hBlock++;
            ans += horizontalCut[h] * vBlock
            h++
        } else {
            vBlock++;
            ans += verticalCut[v] * hBlock
            v++
        }
    }
    while (h < horizontalCut.length) {
        hBlock++;
        ans += horizontalCut[h] * vBlock
        h++
    }
    while (v < verticalCut.length) {
        vBlock++;
        ans += verticalCut[v] * hBlock
        v++
    }
    return ans
};

李恒道

https://leetcode.cn/problems/word-search-ii/submissions/589248008/?envType=study-plan-v2&envId=top-interview-150
树+dfs过了，感觉不像困难

var findWords = function (board, words) {
    const tree = {}
    function insert(str) {
        let node = tree
        for (let index = 0; index < str.length; index++) {
            const char = str[index];
            if (node[char] == undefined) {
                node[char] = {}
            }
            node = node[char]
        }
        node.end = true
        node.str = str
    }
    for (let index = 0; index < words.length; index++) {
        insert(words[index])
    }
    const ans = {}
    const dfs = (x, y, node) => {
        if (x < 0 || y < 0 || x >= board.length || y >= board[0].length) {
            return
        }
        const char = board[x][y]
        if (node[char] !== undefined) {
            if (node[char].end) {
                ans[node[char].str] = true
            }
            board[x][y]=-1
            dfs(x + 1, y, node[char])
            dfs(x - 1, y, node[char])
            dfs(x, y + 1, node[char])
            dfs(x, y - 1, node[char])
            board[x][y]=char
        }

    }
    for (let index = 0; index < board.length; index++) {
        for (let indey = 0; indey < board[0].length; indey++) {
            dfs(index, indey, tree)

        }
    }
    return Object.keys(ans);
};

李恒道

https://leetcode.cn/problems/existence-of-a-substring-in-a-string-and-its-reverse/submissions/589358515/
打卡题
秒了

var isSubstringPresent = function (s) {
    const cache = new Map();
    let lastChar = s[0]
    for (let index = 1; index < s.length; index++) {
        const char = s[index];
        let str = lastChar + char
        cache.set(str, (cache.get(str) ?? 0) + 1)
        lastChar=char
    }
    lastChar = s[s.length - 1]
    for (let index = s.length - 2; index >= 0; index-- ){
        const char = s[index];
        let str = lastChar + char
        if(cache.has(str)){
            return true
        }
        lastChar=char
    }
    return false

};

李恒道

https://leetcode.cn/problems/sign-of-the-product-of-an-array/submissions/589358721/?envType=study-plan-v2&envId=programming-skills、
来个垃圾题

func arraySign(nums []int) int {
    ret:=1
    for i := 0; i < len(nums); i++ {
        num:=nums[i]
        if num<0{
            ret=ret*-1
        }else if num==0{
            return 0
        }else{
            ret=ret*1
        }
    }
    return ret
}

李恒道

https://leetcode.cn/problems/find-occurrences-of-an-element-in-an-array/submissions/589615937/
感觉这是简单题吧

var occurrencesOfElement = function (nums, queries, x) {
  const find = [];
  for (let index = 0; index < nums.length; index++) {
    const num = nums[index];
    if (num == x) {
      find.push(index);
    }
  }
  const ans=[]
  for (let index = 0; index < queries.length; index++) {
    ans.push(find[queries[index]-1]??-1) 
  }
  return ans
};

李恒道

https://leetcode.cn/problems/integer-to-roman/submissions/589619025/?envType=study-plan-v2&envId=top-interview-150
罗马就是这么灭亡的！

const numList = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
const charList = [
  "M",
  "CM",
  "D",
  "CD",
  "C",
  "XC",
  "L",
  "XL",
  "X",
  "IX",
  "V",
  "IV",
  "I",
];
var intToRoman = function (num) {
  let pos = 0;
  let ans = "";
  while (num !== 0) {
    if (num >= numList[pos]) {
      ans += charList[pos];
      num-=numList[pos]
    } else {
      pos++;
      continue;
    }
  }
  return ans;
};