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

李恒道

https://leetcode.cn/submissions/detail/590769689/
线段树，对着大佬提供的集合练就是爽

class Node {
  left;
  right;
  val = 0;
  lazy = 0;
}
class SegmentTreeDynamic {
  root;
  constructor() {
    this.root = new Node();
  }
  buildTree(node, start, end, arr) {
    // 到达叶子节点
    if (start == end) {
      node.val = arr[start];
      return;
    }
    let mid = (start + end) >> 1;
    if (node.left == null) node.left = new Node();
    if (node.right == null) node.right = new Node();
    this.buildTree(node.left, start, mid, arr);
    this. buildTree(node.right, mid + 1, end, arr);
    // 向上更新
    this.pushUp(node);
  }
  update(node, start, end, l, r, val) {
    if (l <= start && end <= r) {
      node.val = (end - start + 1) * val;
      node.lazy = val;
      return;
    }
    let mid = (start + end) >> 1;
    this.pushDown(node, mid - start + 1, end - mid);
    if (l <= mid) this.update(node.left, start, mid, l, r, val);
    if (r > mid) this.update(node.right, mid + 1, end, l, r, val);
    this.pushUp(node);
  }
  pushUp(node) {
    node.val = node.left.val + node.right.val;
  }
  query(node, start, end, l, r) {
    if (l <= start && end <= r) return node.val;
    let mid = (start + end) >> 1,
      ans = 0;
    this.pushDown(node, mid - start + 1, end - mid);
    if (l <= mid) ans += this.query(node.left, start, mid, l, r);
    if (r > mid) ans += this.query(node.right, mid + 1, end, l, r);
    return ans;
  }
  pushDown(node, leftNum, rightNum) {
    if (node.left == null) node.left = new Node();
    if (node.right == null) node.right = new Node();
    if (node.lazy == 0) return;
    node.left.val += node.lazy * leftNum;
    node.right.val += node.lazy * rightNum;
    node.left.lazy += node.lazy;
    node.right.lazy += node.lazy;
    node.lazy = 0;
  }
}

/**
 * @param {number[]} nums
 */
var NumArray = function (nums) {
  this.tree = new SegmentTreeDynamic();
  this.len = nums.length - 1;
  this.tree.buildTree(this.tree.root, 0, nums.length - 1, nums);
};

/**
 * @param {number} index
 * @param {number} val
 * @Return {void}
 */
NumArray.prototype.update = function (index, val) {
   this.tree.update(this.tree.root, 0, this.len, index, index,val);
};

/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function (left, right) {
  return this.tree.query(this.tree.root, 0, this.len, left, right);
};

李恒道

https://leetcode.cn/submissions/detail/590789129/
线段树，到这个基本有感觉了

class Node {
  left;
  right;
  val = 0;
  lazy = 0;
}
class SegmentTreeDynamic {
  root;
  constructor() {
    this.root = new Node();
  }
  update(node, start, end, l, r, val) {
    if (l <= start && end <= r) {
      node.val += val;
      node.lazy += val;
      return;
    }
    let mid = (start + end) >> 1;
    this.pushDown(node, mid - start + 1, end - mid);
    if (l <= mid) this.update(node.left, start, mid, l, r, val);
    if (r > mid) this.update(node.right, mid + 1, end, l, r, val);
    this.pushUp(node);
  }
  pushUp(node) {
    node.val = Math.max(node.left.val, node.right.val);
  }
  query(node, start, end, l, r) {
    if (l <= start && end <= r) return node.val;
    let mid = (start + end) >> 1,
      ans = 0;
    this.pushDown(node, mid - start + 1, end - mid);
    if (l <= mid) ans = this.query(node.left, start, mid, l, r);
    if (r > mid) ans = Math.max(ans,this.query(node.right, mid + 1, end, l, r));
    return ans;
  }
  pushDown(node, leftNum, rightNum) {
    if (node.left == null) node.left = new Node();
    if (node.right == null) node.right = new Node();
    if (node.lazy == 0) return;
    node.left.val += node.lazy;
    node.right.val += node.lazy;
    node.left.lazy += node.lazy;
    node.right.lazy += node.lazy;
    node.lazy = 0;
  }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * var obj = new NumArray(nums)
 * obj.update(index,val)
 * var param_2 = obj.sumRange(left,right)
 */
const max = 10 ** 9;

var MyCalendarTwo = function () {
  this.tree = new SegmentTreeDynamic();
};
/**
 * @param {number} startTime
 * @param {number} endTime
 * @Return {boolean}
 */
MyCalendarTwo.prototype.book = function (startTime, endTime) {
  if (this.tree.query(this.tree.root, 0, max, startTime, endTime - 1) == 2) {
    return false;
  }
  this.tree.update(this.tree.root, 0, max, startTime, endTime - 1, 1);
  return true;
};

李恒道

https://leetcode.cn/submissions/detail/590793109/
卡了一次query，发现写错范围了...

class Node {
  left;
  right;
  val = 0;
  lazy = 0;
}
class SegmentTreeDynamic {
  root;
  constructor() {
    this.root = new Node();
  }
  update(node, start, end, l, r, val) {
    if (l <= start && end <= r) {
      node.val += val;
      node.lazy += val;
      return;
    }
    let mid = (start + end) >> 1;
    this.pushDown(node, mid - start + 1, end - mid);
    if (l <= mid) this.update(node.left, start, mid, l, r, val);
    if (r > mid) this.update(node.right, mid + 1, end, l, r, val);
    this.pushUp(node);
  }
  pushUp(node) {
    node.val = Math.max(node.left.val, node.right.val);
  }
  query(node, start, end, l, r) {
    if (l <= start && end <= r) return node.val;
    let mid = (start + end) >> 1,
      ans = 0;
    this.pushDown(node, mid - start + 1, end - mid);
    if (l <= mid) ans = this.query(node.left, start, mid, l, r);
    if (r > mid) ans = Math.max(ans,this.query(node.right, mid + 1, end, l, r));
    return ans;
  }
  pushDown(node, leftNum, rightNum) {
    if (node.left == null) node.left = new Node();
    if (node.right == null) node.right = new Node();
    if (node.lazy == 0) return;
    node.left.val += node.lazy;
    node.right.val += node.lazy;
    node.left.lazy += node.lazy;
    node.right.lazy += node.lazy;
    node.lazy = 0;
  }
}

const max = 10 ** 9;
var MyCalendarThree = function () {
  this.tree = new SegmentTreeDynamic();
};

/**
 * @param {number} startTime
 * @param {number} endTime
 * @Return {number}
 */
MyCalendarThree.prototype.book = function (startTime, endTime) {
  this.tree.update(this.tree.root, 0, max, startTime, endTime - 1, 1);
  return this.tree.query(this.tree.root, 0, max, 0, max);
};

李恒道

https://leetcode.cn/problems/range-module/submissions/590796944/
抄的模板触碰到边界0了，扣了半天呜呜呜呜

class Node {
  left;
  right;
  val = 0;
  lazy = 0;
}
class SegmentTreeDynamic {
  root;
  constructor() {
    this.root = new Node();
  }
  buildTree(node, start, end, arr) {
    // 到达叶子节点
    if (start == end) {
      node.val = arr[start];
      return;
    }
    let mid = (start + end) >> 1;
    if (node.left == null) node.left = new Node();
    if (node.right == null) node.right = new Node();
    this.buildTree(node.left, start, mid, arr);
    this.buildTree(node.right, mid + 1, end, arr);
    // 向上更新
    this.pushUp(node);
  }
  update(node, start, end, l, r, val) {
    if (l <= start && end <= r) {
      node.val = (end - start + 1) * val;
      node.lazy = val;
      return;
    }
    let mid = (start + end) >> 1;
    this.pushDown(node, mid - start + 1, end - mid);
    if (l <= mid) this.update(node.left, start, mid, l, r, val);
    if (r > mid) this.update(node.right, mid + 1, end, l, r, val);
    this.pushUp(node);
  }
  pushUp(node) {
    node.val = node.left.val + node.right.val;
  }
  query(node, start, end, l, r) {
    if (l <= start && end <= r) return node.val;
    let mid = (start + end) >> 1,
      ans = 0;
    this.pushDown(node, mid - start + 1, end - mid);
    if (l <= mid) ans += this.query(node.left, start, mid, l, r);
    if (r > mid) ans += this.query(node.right, mid + 1, end, l, r);
    return ans;
  }
  pushDown(node, leftNum, rightNum) {
    if (node.left == null) node.left = new Node();
    if (node.right == null) node.right = new Node();
    if (node.lazy == -1) return;
    node.left.val = node.lazy*leftNum;
    node.right.val = node.lazy*rightNum;
    node.left.lazy = node.lazy;
    node.right.lazy = node.lazy;
    node.lazy = -1;
  }
}

var RangeModule = function () {
  this.tree = new SegmentTreeDynamic();
  this.len = 10 ** 9;
};

/**
 * @param {number} left
 * @param {number} right
 * @Return {void}
 */
RangeModule.prototype.addRange = function (left, right) {
  this.tree.update(this.tree.root, 0, this.len, left, right - 1, 1);
};

/**
 * @param {number} left
 * @param {number} right
 * @return {boolean}
 */
RangeModule.prototype.queryRange = function (left, right) {
  return (
    this.tree.query(this.tree.root, 0, this.len, left, right - 1) ==
    right - left
  );
};

/**
 * @param {number} left
 * @param {number} right
 * @return {void}
 */
RangeModule.prototype.removeRange = function (left, right) {
  this.tree.update(this.tree.root, 0, this.len, left, right - 1, 0);
};

李恒道

https://leetcode.cn/problems/falling-squares/submissions/590798903/
线段树的题打的越来越有感觉了

class Node {
  left;
  right;
  val = 0;
  lazy = 0;
}
class SegmentTreeDynamic {
  root;
  constructor() {
    this.root = new Node();
  }
  buildTree(node, start, end, arr) {
    // 到达叶子节点
    if (start == end) {
      node.val = arr[start];
      return;
    }
    let mid = (start + end) >> 1;
    if (node.left == null) node.left = new Node();
    if (node.right == null) node.right = new Node();
    this.buildTree(node.left, start, mid, arr);
    this.buildTree(node.right, mid + 1, end, arr);
    // 向上更新
    this.pushUp(node);
  }
  update(node, start, end, l, r, val) {
    if (l <= start && end <= r) {
      node.val = val;
      node.lazy = val;
      return;
    }
    let mid = (start + end) >> 1;
    this.pushDown(node, mid - start + 1, end - mid);
    if (l <= mid) this.update(node.left, start, mid, l, r, val);
    if (r > mid) this.update(node.right, mid + 1, end, l, r, val);
    this.pushUp(node);
  }
  pushUp(node) {
    node.val = Math.max(node.left.val, node.right.val);
  }
  query(node, start, end, l, r) {
    if (l <= start && end <= r) return node.val;
    let mid = (start + end) >> 1,
      ans = 0;
    this.pushDown(node, mid - start + 1, end - mid);
    if (l <= mid) ans = this.query(node.left, start, mid, l, r);
    if (r > mid)
      ans = Math.max(ans, this.query(node.right, mid + 1, end, l, r));
    return ans;
  }
  pushDown(node, leftNum, rightNum) {
    if (node.left == null) node.left = new Node();
    if (node.right == null) node.right = new Node();
    if (node.lazy == 0) return;
    node.left.val = node.lazy;
    node.right.val = node.lazy;
    node.left.lazy = node.lazy;
    node.right.lazy = node.lazy;
    node.lazy = 0;
  }
}

/**
 * @param {number[][]} positions
 * @Return {number[]}
 */
var fallingSquares = function (positions) {
  let ans=[]
  this.tree = new SegmentTreeDynamic();
  this.len = 10 ** 9;
  for (let index = 0; index < positions.length; index++) {
    const position = positions[index];
    const left= position[0]
    const right=position[0] + position[1]-1
    const add=this.tree.query(this.tree.root, 0, this.len, left, right)+position[1]
    this.tree.update(
      this.tree.root,
      0,
      this.len,
      left,
      right,
      add
    );
    ans.push(this.tree.query(this.tree.root, 0, this.len, 0, this.len))
  }
  return ans
};

李恒道

https://leetcode.cn/problems/longest-increasing-subsequence-ii/submissions/590801293/
这题卡边界了
打个tag后续再练练

class Node {
  left;
  right;
  val = 0;
  lazy = 0;
}
class SegmentTreeDynamic {
  root;
  constructor() {
    this.root = new Node();
  }
  buildTree(node, start, end, arr) {
    // 到达叶子节点
    if (start == end) {
      node.val = arr[start];
      return;
    }
    let mid = (start + end) >> 1;
    if (node.left == null) node.left = new Node();
    if (node.right == null) node.right = new Node();
    this.buildTree(node.left, start, mid, arr);
    this.buildTree(node.right, mid + 1, end, arr);
    // 向上更新
    this.pushUp(node);
  }
  update(node, start, end, l, r, val) {
    if (l <= start && end <= r) {
      node.val = val;
      node.lazy = val;
      return;
    }
    let mid = (start + end) >> 1;
    this.pushDown(node, mid - start + 1, end - mid);
    if (l <= mid) this.update(node.left, start, mid, l, r, val);
    if (r > mid) this.update(node.right, mid + 1, end, l, r, val);
    this.pushUp(node);
  }
  pushUp(node) {
    node.val = Math.max(node.left.val, node.right.val);
  }
  query(node, start, end, l, r) {
    if (l <= start && end <= r) return node.val;
    let mid = (start + end) >> 1,
      ans = 0;
    this.pushDown(node, mid - start + 1, end - mid);
    if (l <= mid) ans = this.query(node.left, start, mid, l, r);
    if (r > mid)
      ans = Math.max(ans, this.query(node.right, mid + 1, end, l, r));
    return ans;
  }
  pushDown(node, leftNum, rightNum) {
    if (node.left == null) node.left = new Node();
    if (node.right == null) node.right = new Node();
    if (node.lazy == 0) return;
    node.left.val = node.lazy;
    node.right.val = node.lazy;
    node.left.lazy = node.lazy;
    node.right.lazy = node.lazy;
    node.lazy = 0;
  }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @Return {number}
 */
var lengthOfLIS = function (nums, k) {
  this.tree = new SegmentTreeDynamic();
  this.max = 10**9;
  let ans = 0;
  for (let index = 0; index < nums.length; index++) {
    const num = nums[index];
    const times =
      this.tree.query(this.tree.root, 0, this.max, num - k, num-1) + 1;
    ans = Math.max(ans, times);
    this.tree.update(this.tree.root, 0, this.max, num , num, times );
  }
  return ans;
};

李恒道

https://leetcode.cn/problems/gray-code/
看了一眼规律

var grayCode = function (n) {
  const ans = [0];
  for (let index = 0; index < n; index++) {
    const size = ans.length;
    for (let pos = size - 1; pos >= 0; pos--) {
      const num = ans[pos];
      ans.push(num|(1<<index))
    }
  }
  return ans;
};

李恒道

https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/submissions/590803244/
看了一眼题解，这个设计的还是挺有复杂度的

var search = function (nums, target) {
  let l = 0,
    r = nums.length - 1;
  while (l <= r) {
    const center = l + Math.floor((r - l) / 2);
    if(nums[center]==target){
      return true
    }
    if (nums[l] == nums[center] && nums[center] == nums[r]) {
      l++;
      r--;
      continue;
    }
    if (nums[l] <= nums[center]) {
      //该部分有序
      if (nums[l] <= target && target <= nums[center]) {
        r = center - 1;
      } else {
        l = center + 1;
      }
    } else {
      if (nums[r] >= target && target >= nums[center]) {
        l = center + 1;
      } else {
        r = center - 1;
      }
    }
  }
  return false
};

李恒道

https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/submissions/590803647/
改改模板1的秒了

var levelOrderBottom = 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.unshift(num);
    }
    stack=nextStack
  } while (stack.length!=0);
  return ret;
};

李恒道

https://leetcode.cn/problems/path-sum-ii/submissions/590804034/
dfs秒了

var pathSum = function (root, targetSum) {
    if(root==null){
        return []
    }
  let ans = [];
  const dfs = (node, arr, sum) => {
    if (node.left === null && node.right == null) {
      if (sum == node.val) {
        arr.push(node.val);
        ans.push([...arr]);
        arr.pop()
      }
      return;
    }
    arr.push(node.val);
    sum -= node.val;
    if (node.left) {
      dfs(node.left, arr, sum);
    }
    if (node.right) {
      dfs(node.right, arr, sum);
    }
    arr.pop();
  };
  dfs(root, [], targetSum);
  return ans
};