【刷题小助手】贡献模板代码，成为开源项目的贡献者

[azl397985856]

目前我们的模板代码语言还不多，希望大家可以加入我们，造福更多的打工人。

直接在评论区回复你要添加的模板名字以及你要增加的新的编程语言的代码即可。

[shaoyuanhangyes]

543. 二叉树的直径

题解代码为Cpp

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if(root==NULL) return 0;
        diameter=1;
        maxDepth(root);
        return diameter-1;
    }
    int maxDepth(TreeNode* root){
        if(root==NULL) return 0;
        int l_left=maxDepth(root->left);
        int l_right=maxDepth(root->right);
        diameter=max(diameter,l_left+l_right+1);
        return max(l_left,l_right)+1;
    }
private:
    int diameter;
};

[yearkey-cy]

295. 数据流的中位数

题解代码为Cpp

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }
    
    void addNum(int num) {
        if (big_queue.empty()) {
            big_queue.push(num);
            return;
        }
        if (big_queue.size() == small_queue.size()) {
            if (num <= big_queue.top()) {
                big_queue.push(num);
            } else {
                small_queue.push(num);
            }
        } else if (big_queue.size() > small_queue.size()) {
            if (big_queue.top() > num) {
                small_queue.push(big_queue.top());
                big_queue.pop();
                big_queue.push(num);
            } else {
                small_queue.push(num);
            }
        } else if (big_queue.size() < small_queue.size()) {
            if (small_queue.top() > num) {
                big_queue.push(num);
            } else {
                big_queue.push(small_queue.top());
                small_queue.pop();
                small_queue.push(num);
            }
        }
    }
    
    double findMedian() {
        if (big_queue.size() == small_queue.size()) {
            return (big_queue.top() + small_queue.top()) * 0.5;
        }
        if (big_queue.size() < small_queue.size()) {
            return small_queue.top();
        }
        return big_queue.top();
    }

private:
    std::priority_queue<int, std::vector<int>, std::greater<int>> small_queue;  // 最小堆
    std::priority_queue<int> big_queue; // 最大堆
};

[azl397985856]

295. 数据流的中位数

题解代码为Cpp

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }
    
    void addNum(int num) {
        if (big_queue.empty()) {
            big_queue.push(num);
            return;
        }
        if (big_queue.size() == small_queue.size()) {
            if (num <= big_queue.top()) {
                big_queue.push(num);
            } else {
                small_queue.push(num);
            }
        } else if (big_queue.size() > small_queue.size()) {
            if (big_queue.top() > num) {
                small_queue.push(big_queue.top());
                big_queue.pop();
                big_queue.push(num);
            } else {
                small_queue.push(num);
            }
        } else if (big_queue.size() < small_queue.size()) {
            if (small_queue.top() > num) {
                big_queue.push(num);
            } else {
                big_queue.push(small_queue.top());
                small_queue.pop();
                small_queue.push(num);
            }
        }
    }
    
    double findMedian() {
        if (big_queue.size() == small_queue.size()) {
            return (big_queue.top() + small_queue.top()) * 0.5;
        }
        if (big_queue.size() < small_queue.size()) {
            return small_queue.top();
        }
        return big_queue.top();
    }

private:
    std::priority_queue<int, std::vector<int>, std::greater<int>> small_queue;  // 最小堆
    std::priority_queue<int> big_queue; // 最大堆
};

thank u~

[yearkey-cy]

376. 摆动序列

题解代码为Cpp

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {

        if (nums.size() < 2) return nums.size();

        static const int STATE_BEGIN = 0;
        static const int STATE_UP = 1;
        static const int STATE_DOWN = 2;
        int max_length = 1;
        int STATE = STATE_BEGIN;
        for (int i = 1; i < nums.size(); ++i) {
            switch(STATE) {
                case STATE_BEGIN:
                    if (nums[i-1] < nums[i]) {
                        STATE = STATE_UP;
                        ++max_length;
                    } else if (nums[i-1] > nums[i]) {
                        STATE = STATE_DOWN;
                        ++max_length;
                    }
                break;
                case STATE_UP:
                    if (nums[i-1] > nums[i]) {
                        STATE = STATE_DOWN;
                        ++max_length;
                    }
                break;
                case STATE_DOWN:
                    if (nums[i-1] < nums[i]) {
                        STATE = STATE_UP;
                        ++max_length;
                    }
                break;
            }
        }
        return max_length;
    }
};

[suukii]

二分查找

寻找最左插入位置

JavaScript Code

/**
 * @description 寻找最左插入位置
 * @param {number[]} nums 
 * @param {number} x 
 * @returns {number}
 */
function searchInsertLeft(nums, x) {
  // 题意转换一下，其实就是寻找第一个“大于等于” x 的数字，返回它的下标
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);

    if (nums[mid] >= x) right = mid - 1;
    if (nums[mid] < x) left = mid + 1;
  }

  return left;
}

寻找最右插入位置

JavaScript Code

/**
 * @description 寻找最右插入位置
 * @param {number[]} nums 
 * @param {number} x 
 * @returns {number}
 */
function searchInsertRight(nums, x) {
  // 题意转换一下，其实就是寻找第一个“大于” x 的数字，返回它的下标
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);

    if (nums[mid] > x) right = mid - 1;
    if (nums[mid] <= x) left = mid + 1;
  }

  return left;
}

搜索旋转排序数组

JavaScript Code

/**
 * @description 搜索旋转排序数组
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchRotate = function (nums, target) {
  let l = 0,
    r = nums.length - 1;
  while (l <= r) {
    const m = l + ((r - l) >> 1);
    if (nums[m] === target) return m;

    // 将重复元素排除在搜索区间外
    while (l < m && nums[l] === nums[m]) {
      l++;
    }

    // m 位于左侧有序部分
    if (nums[l] <= nums[m]) {
      // m 大于 target，并且 target 大于左侧最小值，才缩小右边界
      if (nums[m] > target && target >= nums[l]) r = m - 1;
      else l = m + 1;
    }
    // m 位于右侧有序部分
    else {
      // m 小于 target，并且 target 小于右侧最大值，才缩小左边界
      if (nums[m] < target && target <= nums[r]) l = m + 1;
      else r = m - 1;
    }
  }
  return -1;
};

[azl397985856]

@suukii 搜索旋转数组似乎没有这个模板吧？

[azl397985856]

@suukii 最左最右插入模板已更新，下次发布就会有

[suukii]

@azl397985856 好像是没有搜索旋转数组这个模板，一时 CV high 了(⓿_⓿)

[azl397985856]

@suukii doge

[981377660LMT]

注意到了不带权并查集模板的一个小地方:

class UF:
  def __init__(self, M):
      self.parent = {}
      self.cnt = 0
      # 初始化 parent，size 和 cnt
      for i in range(M):
          self.parent[i] = i
          self.cnt += 1

  def find(self, x):
      if x != self.parent[x]:
          self.parent[x] = self.find(self.parent[x])
          return self.parent[x]
      return x
  def union(self, p, q):
      if self.connected(p, q): return
      leader_p = self.find(p)
      leader_q = self.find(q)
      self.parent[leader_p] = leader_q
      self.cnt -= 1
  def connected(self, p, q):
      return self.find(p) == self.find(q)

union这一步，如果这个地方

self.parent[leader_p] = leader_q

能够保证大的根总是指向小的根(如果根支持比较的话)，效率会好一些

我在做题 leetcode1202交换字符串中的元素 的时候
将

  const union = (key1: number, key2: number) => {
    const root1 = find(key1)
    const root2 = find(key2)
    parent[root1] = parent[root2]
  }

改为

  const union = (key1: number, key2: number) => {
    const root1 = find(key1)
    const root2 = find(key2)
    parent[Math.max(root1, root2)] = Math.min(root1, root2)
  }

后，时间从平均 8000 ms 降到了平均 200ms

[981377660LMT]

旋转二维矩阵

// 顺时针旋转90度
const rotateMatrix = function (mat: number[][]): number[][] {
  const m = mat.length
  const n = mat[0].length
  const res = Array.from<number, number[]>({ length: n }, () => Array(m).fill(0))

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      res[j][m - i - 1] = mat[i][j]
    }
  }

  return res
}

[981377660LMT]

ts 线段树

class SegmentTree<S>{
  private data: S[]
  private tree: S[]
  private mergeFunc: (a: S, b: S) => S

  constructor(arr: S[], mergeFunc: (a: S, b: S) => S) {
    this.data = arr.slice()
    this.tree = Array<S>(this.data.length * 4)
    this.mergeFunc = mergeFunc
    this.buildSegementTree(0, 0, this.data.length - 1)
  }


  private buildSegementTree(rootIndex: number, left: number, right: number): void {
    if (left === right) {
      this.tree[rootIndex] = this.data[left]
      return
    }

    const mid = (left + right) >> 1
    const leftTreeIndex = this.leftChild(rootIndex)
    const rightTreeIndex = this.rightChild(rootIndex)
    this.buildSegementTree(leftTreeIndex, left, mid)
    this.buildSegementTree(rightTreeIndex, mid + 1, right)

    this.tree[rootIndex] = this.mergeFunc(this.tree[leftTreeIndex], this.tree[rightTreeIndex])
  }


  query(left: number, right: number): S {
    return this._query(0, 0, this.data.length - 1, left, right)
  }

  private _query(
    rootIndex: number,
    left: number,
    right: number,
    queryLeft: number,
    queryRight: number
  ): S {
    if (left === queryLeft && right === queryRight) return this.tree[rootIndex]

    const mid = (left + right) >> 1
    const leftTreeIndex = this.leftChild(rootIndex)
    const rightTreeIndex = this.rightChild(rootIndex)
    if (queryLeft >= mid + 1) {
      // query的整个范围在右边
      return this._query(rightTreeIndex, mid + 1, right, queryLeft, queryRight)
    } else if (queryRight <= mid) {
      // query的整个范围在左边
      return this._query(leftTreeIndex, left, mid, queryLeft, queryRight)
    } else {
      // 左边找左边的query范围
      const leftResult = this._query(leftTreeIndex, left, mid, queryLeft, mid)
      // 右边找右边的query范围
      const rightResult = this._query(rightTreeIndex, mid + 1, right, mid + 1, queryRight)

      return this.mergeFunc(leftResult, rightResult)
    }
  }

  update(index: number, val: S): void {
    this.data[index] = val
    this._update(0, 0, this.data.length - 1, index, val)
  }

  private _update(rootIndex: number, left: number, right: number, index: number, val: S): void {
    if (left === right) {
      this.tree[rootIndex] = val
      return
    }

    const mid = (left + right) >> 1
    const leftTreeIndex = this.leftChild(rootIndex)
    const rightTreeIndex = this.rightChild(rootIndex)
    if (index >= mid + 1) {
      this._update(rightTreeIndex, mid + 1, right, index, val)
    } else if (index <= mid) {
      this._update(leftTreeIndex, left, mid, index, val)
    }

    this.tree[rootIndex] = this.mergeFunc(this.tree[leftTreeIndex], this.tree[rightTreeIndex])
  }

  private leftChild(index: number) {
    return 2 * index + 1
  }

  private rightChild(index: number) {
    return 2 * index + 2
  }
}

[azl397985856]

@yearkey-cy 376 并没有被我收录

[981377660LMT]

typescript 树状数组

class BIT {
  private size: number
  private tree: number[]

  constructor(size: number) {
    this.size = size
    this.tree = Array(size + 1).fill(0)
  }

    /**
   *
   * @param x (离散化后)的树状数组索引
   * @param k 增加的值
   * @description
   * 单点修改：tree数组下标x处的值加k
   */
  add(x: number, k: number) {
    if (x <= 0) throw Error('查询索引应为正整数')
    for (let i = x; i <= this.size; i += this.lowbit(i)) {
      this.tree[i] += k
    }
  }

  /**
   *
   * @param x
   * @description
   * 区间查询：返回前x项的值
   */
  query(x: number) {
    let res = 0
    for (let i = x; i > 0; i -= this.lowbit(i)) {
      res += this.tree[i]
    }
    return res
  }

  private lowbit(x: number) {
    return x & -x
  }
}

离散化+查询更新
相同模板解决三道困难
315. 计算右侧小于当前元素的个数
327. 区间和的个数
493. 翻转对