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

azl397985856 · 2020-12-07T10:44:53Z

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

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

shaoyuanhangyes · 2020-12-08T14:19:59Z

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 · 2020-12-17T07:13:34Z

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 · 2020-12-17T11:15:16Z

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 · 2020-12-22T03:55:00Z

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 · 2021-01-07T05:36:03Z

二分查找

寻找最左插入位置

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 · 2021-01-09T12:58:48Z

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

azl397985856 · 2021-01-09T13:00:31Z

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

suukii · 2021-01-11T01:13:47Z

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

azl397985856 · 2021-01-11T06:22:41Z

@suukii doge

981377660LMT · 2021-08-22T13:01:41Z

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

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 · 2021-08-22T13:34:41Z

旋转二维矩阵

// 顺时针旋转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 · 2021-08-23T03:27:51Z

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 · 2021-08-28T05:32:16Z

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

981377660LMT · 2021-09-15T06:04:13Z

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. 翻转对

981377660LMT · 2021-09-29T03:01:32Z

双向bfs

interface GetNextState<State> {
  (curState: State): State[]
}

/**
 *
 * @param start
 * @param target
 * @param getNextState
 * @returns start 到 target 的最短距离
 *
 */
function bibfs<State = string>(
  start: State,
  target: State,
  getNextState: GetNextState<State>
): number {
  let queue1 = new Set<State>([start])
  let queue2 = new Set<State>([target])
  const visited = new Set()
  let steps = 0

  while (queue1.size && queue2.size) {
    if (queue1.size > queue2.size) {
      ;[queue1, queue2] = [queue2, queue1]
    }

    // 本层搜出来的结果
    const nextQueue = new Set<State>()

    for (const cur of queue1) {
      if (queue2.has(cur)) return steps

      if (visited.has(cur)) continue
      visited.add(cur)

      for (const next of getNextState(cur)) {
        nextQueue.add(next)
      }
    }

    steps++
    ;[queue1, queue2] = [queue2, nextQueue]
  }

  return -1
}

981377660LMT · 2021-10-30T01:25:54Z

二分图检测

const enum Color {
  Red = 0,
  Black,
  Unvisited,
}

/**
 * @param {number[][]} adjList 邻接表
 * @return {boolean}
 */
const isBipartite = (adjList: number[][]): boolean => {
  let res = true
  const colors = Array<Color>(adjList.length).fill(Color.Unvisited)

  for (let i = 0; i < adjList.length; i++) {
    if (colors[i] === Color.Unvisited) dfs(i, Color.Red)
  }

  return res

  function dfs(cur: number, color: Color) {
    colors[cur] = color

    for (const next of adjList[cur]) {
      if (colors[next] === Color.Unvisited) {
        dfs(next, color ^ 1)
      } else {
        if (colors[cur] === colors[next]) {
          return (res = false)
        }
      }
    }
  }
}

console.log(
  isBipartite([
    [1, 3],
    [0, 2],
    [1, 3],
    [0, 2],
  ])
)

981377660LMT · 2021-10-30T01:29:33Z

寻找二分图的最大匹配

function hungarian(adjList: number[][]): number {
  let maxMatching = 0
  let visited: boolean[]
  const matching = Array<number>(adjList.length).fill(-1)

  const colors = bisect(adjList)
  for (let i = 0; i < adjList.length; i++) {
    // 从二分图的左侧还没有匹配到的点出发，dfs寻找增广路径。如果找到，最大匹配数就加一。
    if (colors[i] === 0 && matching[i] === -1) {
      visited = Array<boolean>(adjList.length).fill(false)
      if (dfs(i)) maxMatching++
    }
  }

  return maxMatching

  // 匈牙利算法核心:寻找增广路径 找到的话最大匹配加一
  // dfs(cur) 表示给cur找匹配
  function dfs(cur: number): boolean {
    if (visited[cur]) return false
    visited[cur] = true

    for (const next of adjList[cur]) {
      // 是增广路径或者dfs找到增广路径
      if (matching[next] === -1 || dfs(matching[next])) {
        matching[cur] = next
        matching[next] = cur
        return true
      }
    }

    return false
  }

  // 二分图检测、获取colors
  function bisect(adjList: number[][]) {
    const colors = Array<number>(adjList.length).fill(-1)

    const dfs = (cur: number, color: number) => {
      colors[cur] = color
      for (const next of adjList[cur]) {
        if (colors[next] === -1) {
          dfs(next, color ^ 1)
        } else {
          if (colors[next] === colors[cur]) {
            throw new Error('不是二分图')
          }
        }
      }
    }

    for (let i = 0; i < adjList.length; i++) {
      if (colors[i] === -1) dfs(i, 0)
    }

    return colors
  }
}

console.log(hungarian([[1, 3], [0, 2], [1], [0], [], []])) // 2

azl397985856 added the 多编程语言 label Dec 7, 2020

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

azl397985856 commented Dec 7, 2020 •

edited

Loading

shaoyuanhangyes commented Dec 8, 2020

yearkey-cy commented Dec 17, 2020

azl397985856 commented Dec 17, 2020

295. 数据流的中位数

yearkey-cy commented Dec 22, 2020

suukii commented Jan 7, 2021 •

edited

Loading

azl397985856 commented Jan 9, 2021

azl397985856 commented Jan 9, 2021

suukii commented Jan 11, 2021

azl397985856 commented Jan 11, 2021

981377660LMT commented Aug 22, 2021

981377660LMT commented Aug 22, 2021

981377660LMT commented Aug 23, 2021

azl397985856 commented Aug 28, 2021

981377660LMT commented Sep 15, 2021

981377660LMT commented Sep 29, 2021

981377660LMT commented Oct 30, 2021

981377660LMT commented Oct 30, 2021

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

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

Comments

azl397985856 commented Dec 7, 2020 • edited Loading

shaoyuanhangyes commented Dec 8, 2020

543. 二叉树的直径

yearkey-cy commented Dec 17, 2020

295. 数据流的中位数

azl397985856 commented Dec 17, 2020

295. 数据流的中位数

yearkey-cy commented Dec 22, 2020

376. 摆动序列

suukii commented Jan 7, 2021 • edited Loading

二分查找

寻找最左插入位置

寻找最右插入位置

搜索旋转排序数组

azl397985856 commented Jan 9, 2021

azl397985856 commented Jan 9, 2021

suukii commented Jan 11, 2021

azl397985856 commented Jan 11, 2021

981377660LMT commented Aug 22, 2021

981377660LMT commented Aug 22, 2021

981377660LMT commented Aug 23, 2021

azl397985856 commented Aug 28, 2021

981377660LMT commented Sep 15, 2021

981377660LMT commented Sep 29, 2021

981377660LMT commented Oct 30, 2021

981377660LMT commented Oct 30, 2021

azl397985856 commented Dec 7, 2020 •

edited

Loading

suukii commented Jan 7, 2021 •

edited

Loading