论坛 › 其它 › 【当前排名67359】挑战leetcode进入前1w名

李恒道 发表于 2025-1-2 23:47:06

https://leetcode.cn/submissions/detail/590769689/
线段树，对着大佬提供的集合练就是爽
```js
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;
      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);
};
```

李恒道 发表于 2025-1-2 23:47:29

https://leetcode.cn/submissions/detail/590789129/
线段树，到这个基本有感觉了
```js
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;
};
```

李恒道 发表于 2025-1-2 23:47:54

https://leetcode.cn/submissions/detail/590793109/
卡了一次query，发现写错范围了...
```js
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);
};

```

李恒道 发表于 2025-1-3 00:11:28

https://leetcode.cn/problems/range-module/submissions/590796944/
抄的模板触碰到边界0了，扣了半天呜呜呜呜
```js
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;
      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);
};
```

李恒道 发表于 2025-1-3 00:32:06

https://leetcode.cn/problems/falling-squares/submissions/590798903/
线段树的题打的越来越有感觉了
```js
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;
      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;
    const left= position
    const right=position + position-1
    const add=this.tree.query(this.tree.root, 0, this.len, left, right)+position
    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
};
```

李恒道 发表于 2025-1-3 01:08:20

https://leetcode.cn/problems/longest-increasing-subsequence-ii/submissions/590801293/
这题卡边界了
打个tag后续再练练
```js
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;
      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;
    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;
};
```

李恒道 发表于 2025-1-3 01:21:34

https://leetcode.cn/problems/gray-code/
看了一眼规律
```js
var grayCode = function (n) {
const ans = ;
for (let index = 0; index < n; index++) {
    const size = ans.length;
    for (let pos = size - 1; pos >= 0; pos--) {
      const num = ans;
      ans.push(num|(1<<index))
    }
}
return ans;
};
```

李恒道 发表于 2025-1-3 01:52:43

https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/submissions/590803244/
看了一眼题解，这个设计的还是挺有复杂度的
```js
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==target){
      return true
    }
    if (nums == nums && nums == nums) {
      l++;
      r--;
      continue;
    }
    if (nums <= nums) {
      //该部分有序
      if (nums <= target && target <= nums) {
      r = center - 1;
      } else {
      l = center + 1;
      }
    } else {
      if (nums >= target && target >= nums) {
      l = center + 1;
      } else {
      r = center - 1;
      }
    }
}
return false
};
```

李恒道 发表于 2025-1-3 02:06:50

https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/submissions/590803647/
改改模板1的秒了
```js
var levelOrderBottom = function (root) {
const ret = [];
let stack = ;
do {
    const nextStack = [];
    const num = [];
    for (let index = 0; index < stack.length; index++) {
      const node = stack;
      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;
};
```

李恒道 发表于 2025-1-3 02:23:50

https://leetcode.cn/problems/path-sum-ii/submissions/590804034/
dfs秒了
```js
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
};
```

查看完整版本: 【当前排名67359】挑战leetcode进入前1w名