Skip to content

Instantly share code, notes, and snippets.

@HelKyle

HelKyle/leetcode-utils.js

Last active April 30, 2023 02:21
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save HelKyle/86d5f314a191f2688d06a5094251d3e3 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save HelKyle/86d5f314a191f2688d06a5094251d3e3 to your computer and use it in GitHub Desktop.
Download ZIP
Leetcode Javascript Utils
Raw
leetcode-utils.js
// 二分找下限
function lower_bound(nums, target) {
let lo = 0, hi = nums.length;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (nums[mid] >= target) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
// 二分找上限
function upper_bound(nums, target) {
let lo = 0, hi = nums.length;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (nums[mid] > target) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
// 并查集
class UnionFind {
constructor (n) {
this.parent = new Array(n).fill(0).map((element, index) => index);
this.size = new Array(n).fill(1);
// 当前连通分量数目
this.setCount = n;
}
findset (x) {
if (this.parent[x] === x) {
return x;
}
this.parent[x] = this.findset(this.parent[x]);
return this.parent[x];
}
unite (a, b) {
let x = this.findset(a), y = this.findset(b);
if (x === y) {
return false;
}
if (this.size[x] < this.size[y]) {
[x, y] = [y, x];
}
this.parent[y] = x;
this.size[x] += this.size[y];
this.setCount -= 1;
return true;
}
connected (a, b) {
const x = this.findset(a), y = this.findset(b);
return x === y;
}
}
// BigInt 支持 N 次方
let L = 2n ** BigInt(p)
// 大整数快 pow + mod
const mod = BigInt(1e9 + 7)
function pow(b, p) {
if (p === 0n) return 1n
if (p === 1n) return b
if (p % 2n) {
return pow(b, p - 1n) * b % mod
}
let h = pow(b, p / 2n)
return h * h % mod
}
// 二分取中间
const mid = l + ((r - l) >> 1);
// 最大公约数
function gcd (a, b) {
if (a % b === 0) {
return b
}
return gcd(b, a % b)
}
// 最小公倍数
function lcm(a,b){
return (a*b) / gcd(a,b);
}
@HelKyle
Copy link
Author

HelKyle commented Nov 12, 2022 •
edited
Loading 

class Heap {
  constructor (compare = (a, b) => a - b) {
    this.compare = compare
    this.list = []
  }

  get size () {
    return this.list.length
  }

  get top () {
    return this.list[0]
  }

  left (index) {
    return index * 2 + 1
  }

  right (index) {
    return index * 2 + 2
  }

  parent (index) {
    return (index - 1) >> 1
  }

  swap (index1, index2) {
    [this.list[index1], this.list[index2]] = [this.list[index2], this.list[index1]]
  }

  heapify (index) {
    const leftIndex = this.left(index)
    const rightIndex = this.right(index)
    let cur = index

    if (this.list[leftIndex] !== undefined && this.compare(this.list[cur], this.list[leftIndex]) > 0) {
      cur = leftIndex
    }
    if (this.list[rightIndex] !== undefined && this.compare(this.list[cur], this.list[rightIndex]) > 0) {
      cur = rightIndex
    } 

    if (cur !== index) {
      this.swap(cur, index)
      this.heapify(cur)
    }
  }

  insert(node) {
    this.list.push(node)
    let cur = this.size - 1
    let parentIndex = this.parent(cur)

    while (cur > 0 && this.compare(this.list[parentIndex], this.list[cur]) > 0) {
      this.swap(cur, parentIndex)
      cur = parentIndex
      parentIndex = this.parent(cur)
    }
  }

  remove() {
    this.swap(0, this.size - 1)
    const result = this.list.pop()
    this.heapify(0)
    return result
  }
}

@HelKyle
Copy link
Author

HelKyle commented Dec 24, 2022 •
edited
Loading

计算 n 内不能被 divisor 整除的正整数有多少个：

Math.floor(n / divisor) * (divisor - 1) + (n % divisor)

@HelKyle
Copy link
Author

HelKyle commented Jan 1, 2023

找出一个前面的质数

const max = 1e6 + 33
const primes = []
const is_primes = new Array(max).fill(1)
for (let i = 2; i < max; i ++) {
    if (is_primes[i] === 1) {
        primes.push(i)
        for (let j = i * i; j < max; j += i) {
            is_primes[j] = 0
        }
    }
}

@HelKyle
Copy link
Author

HelKyle commented Jan 1, 2023

计算所有质因子

function getPrimeFactor(num) {
    res = []
    for (let i = 2; i < Math.sqrt(num) + 1; i ++) {
        let cnt = 0
        while ((num % i) === 0) {
            num /= i
            cnt += 1
        }
        if (cnt) {
            res.push([i, cnt])
        }
        if (i > num) {
            break
        }
    }
    if (num !== 1 || res.length === 0) {
        res.push([num, 1])
    }
    return res
}

@HelKyle
Copy link
Author

HelKyle commented Apr 30, 2023

矩阵遍历

const dirs = [
      [-1, 0],
      [0, -1],
      [1, 0],
      [0, 1]
  ]
  const visited = new Array(grid.length).fill(0)
      .map(() => new Array(grid[0].length).fill(0))
  let ans = 0
  
  function dfs (i, j) {
      if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) {
          return 0
      }
      if (grid[i][j] === 0 || visited[i][j]) {
          return 0
      }
      visited[i][j] = 1
      let cur = grid[i][j]
      for (const [di, dj] of dirs) {
          cur += dfs(i + di, j + dj, cur)
      }
      return cur
  }
  
  for (let i = 0; i < grid.length; i ++) {
      for (let j = 0; j < grid[0].length; j ++) {
          if (!visited[i][j]) {
              ans = Math.max(ans, dfs(i, j))
          }
      }
  }
  return ans

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment