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

李恒道

https://leetcode.cn/problems/sfvd7V/
相同题

/**
 * @param {string[]} strs
 * @Return {string[][]}
 */
var groupAnagrams = function (strs) {
  const obj = strs.reduce((obj, value) => {
    const name = value.split("").sort().join("");
    (obj[name] = obj[name] ?? []), obj[name].push(value);
    return obj;
  }, {});
  const arr = [];
  for (const key in obj) {
    arr.push(obj[key]);
  }
  return arr;
};

李恒道

https://leetcode.cn/problems/not-boring-movies/submissions/595969135/?envType=study-plan-v2&envId=sql-free-50
秒了

# Write your MySQL query statement below
SELECT cinema.* FROM cinema WHERE   id%2!=0&&description!="boring" ORDER BY rating DESC

李恒道

https://leetcode.cn/problems/ugly-number-ii/submissions/595972540/
最小堆，这题没想出来，真妙

/**
 * @param {number} n
 * @Return {number}
 */
class Heap {
  constructor(comparator = (a, b) => a - b) {
    this.heap = [];
    this.comparator = comparator;
  }

  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  getLeftChildIndex(index) {
    return 2 * index + 1;
  }

  getRightChildIndex(index) {
    return 2 * index + 2;
  }

  swap(index1, index2) {
    const temp = this.heap[index1];
    this.heap[index1] = this.heap[index2];
    this.heap[index2] = temp;
  }

  insert(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = this.getParentIndex(index);
      if (this.comparator(this.heap[index], this.heap[parentIndex]) < 0) {
        this.swap(index, parentIndex);
        index = parentIndex;
      } else {
        break;
      }
    }
  }

  extractMin() {
    if (this.heap.length === 0) {
      return null;
    }
    if (this.heap.length === 1) {
      return this.heap.pop();
    }
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown(0);
    return min;
  }

  heapifyDown(index) {
    let smallest = index;
    const leftChildIndex = this.getLeftChildIndex(index);
    const rightChildIndex = this.getRightChildIndex(index);

    if (
      leftChildIndex < this.heap.length &&
      this.comparator(this.heap[leftChildIndex], this.heap[smallest]) < 0
    ) {
      smallest = leftChildIndex;
    }

    if (
      rightChildIndex < this.heap.length &&
      this.comparator(this.heap[rightChildIndex], this.heap[smallest]) < 0
    ) {
      smallest = rightChildIndex;
    }

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

  peek() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }

  size() {
    return this.heap.length;
  }
}
var nthUglyNumber = function (n) {
  const minHeap = new Heap((a, b) => a - b);
  minHeap.insert(1);
  const visit = new Set();
  let ugly = 0;
  let list = [2, 3, 5];
  for (let index = 0; index < n; index++) {
    ugly = minHeap.extractMin();
    for (const num of list) {
      const mul = num * ugly;
      if (!visit.has(mul)) {
        visit.add(mul);
        minHeap.insert(mul);
      }
    }
  }
  return ugly;
};

李恒道

https://leetcode.cn/problems/chou-shu-lcof/submissions/595973028/
lru，一个题

/**
 * @param {number} n
 * @Return {number}
 */
class Heap {
  constructor(comparator = (a, b) => a - b) {
    this.heap = [];
    this.comparator = comparator;
  }

  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  getLeftChildIndex(index) {
    return 2 * index + 1;
  }

  getRightChildIndex(index) {
    return 2 * index + 2;
  }

  swap(index1, index2) {
    const temp = this.heap[index1];
    this.heap[index1] = this.heap[index2];
    this.heap[index2] = temp;
  }

  insert(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = this.getParentIndex(index);
      if (this.comparator(this.heap[index], this.heap[parentIndex]) < 0) {
        this.swap(index, parentIndex);
        index = parentIndex;
      } else {
        break;
      }
    }
  }

  extractMin() {
    if (this.heap.length === 0) {
      return null;
    }
    if (this.heap.length === 1) {
      return this.heap.pop();
    }
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown(0);
    return min;
  }

  heapifyDown(index) {
    let smallest = index;
    const leftChildIndex = this.getLeftChildIndex(index);
    const rightChildIndex = this.getRightChildIndex(index);

    if (
      leftChildIndex < this.heap.length &&
      this.comparator(this.heap[leftChildIndex], this.heap[smallest]) < 0
    ) {
      smallest = leftChildIndex;
    }

    if (
      rightChildIndex < this.heap.length &&
      this.comparator(this.heap[rightChildIndex], this.heap[smallest]) < 0
    ) {
      smallest = rightChildIndex;
    }

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

  peek() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }

  size() {
    return this.heap.length;
  }
}
var nthUglyNumber = function (n) {
  const minHeap = new Heap((a, b) => a - b);
  minHeap.insert(1);
  const visit = new Set();
  let ugly = 0;
  let list = [2, 3, 5];
  for (let index = 0; index < n; index++) {
    ugly = minHeap.extractMin();
    for (const num of list) {
      const mul = num * ugly;
      if (!visit.has(mul)) {
        visit.add(mul);
        minHeap.insert(mul);
      }
    }
  }
  return ugly;
};

李恒道

https://leetcode.cn/problems/reverse-string-ii/submissions/596001041/
过年题简单

var reverseStr = function (s, k) {
  s = s.split("");
  let base = 0;
  let ans = "";
  while (base < s.length) {
    ans += s.slice(base, base + k).reverse().join("");
    ans += s.slice( base + k, base + k+k).join("")
    base+=k
    base+=k
  }
  return ans
};

李恒道

https://leetcode.cn/problems/reverse-string/submissions/596001145/
过了

var reverseString = function(s) {
    for (let index = 0; index < s.length/2; index++) {
     const temp=s[index];
     s[index]=s[s.length-1-index];
     s[s.length-1-index]=temp
    }
};

李恒道

https://leetcode.cn/problems/6eUYwP/submissions/596002336/
秒了

var pathSum = function (root, targetSum) {
  const map = new Map();
  map.set(0,1)
  let ret = 0;
  let presum = 0;
  const dfs = (root) => {
    if(root==null){
      return
    }
    const haveNum =presum- (targetSum - root.val);
    if (map.has(haveNum)) {
      ret += map.get(haveNum);
    }
    presum += root.val;
    if (map.has(presum)) {
      map.set(presum, map.get(presum) + 1);
    } else {
      map.set(presum, 1);
    }
    dfs(root.left);
    dfs(root.right);
    map.set(presum, map.get(presum) - 1);
    presum -= root.val;
  };
  dfs(root);
  return ret;
};