(2024下) 装作是博客 - 问题

[zunsthy]

wec

一、

1. 共有 n 个，2人，每次拿 a~b 个，拿到最后一个赢

不能赢则返回 false

function win(n, a, b) {
  return function(x) {
    n -= x
    if (n === 1) return 1
    const y = (x - 1) % (a + b)
    if (y < a) return false
    n -= y
    return y
  }
}

2. 大数相乘

采用竖式乘法

function floor(x) { return Math.floor(x) }
function join(arr) {
  let r = ''
  let i = 0
  while (arr[i] == 0) i++
  while (i < arr.length) r += arr[i++]
  return r || '0'
}
function multiply(n1, n2) {
  const len1 = n1.length
  const len2 = n2.length
  const lenr = len1 + len2
  const r = new Array(lenr)
  r.fill(0)
  function acc(x, d) {
    while (x) {
      r[d] += x
      if (r[d] >= 10) {
        x = floor(r[d] / 10)
        r[d] %= 10
      } else {
        x = 0
      }
      d++
    }
  }
  for (let i = 0; i < len1; i++)
  for (let j = 0; j < len2; j++) {
    const d1 = len1 - i - 1
    const d2 = len2 - j - 1
    acc(n1[i] * n2[j], d1 + d2)
  }
  return join(r.reverse())
}

随机一些数据，检查正确性

function random(n) { return Math.floor(Math.random() * n) }
function r(d) { return Array(random(d)).fill(0).map(() => random(10)).join('') }
for (let i = 0; i < 100; i++) {
  const a = r(200);
  const b = r(300);
  if ((BigInt(a) * BigInt(b)).toString(10) !== multiply(a, b)) {
    throw new Error(`error by ${a} x ${b}`);
  }
}
console.log('done')

二、

[zunsthy]

、

1. 找出第K大

需要一个堆

function li(i) { return (i << 1) + 1 }
function pi(i) { return (i - 1) >> 1 }
function Heap(arr = [], cmp = (a, b) => a < b) {
    const h = []
  const swap = (i, j) => {
    [h[i], h[j]] = [h[j], h[i]]
  }
  const pop = () => {
    swap(0, h.length - 1)
    const top = h.pop()
    let i = 0, c
    while ((c = li(i)) < h.length) {
      let j = c
      if (c + 1 < h.length && cmp(h[c + 1], h[c]))
        j = c + 1
      if (cmp(h[i], h[j])) break;
      swap(i, j)
      i = j
    }
    return top
  }
  const push = (x) => {
    let i = h.push(x) - 1
    while (i) {
      const p = pi(i)
      if (cmp(h[p], h[i])) break
      swap(p, i)
      i = p
    }
  }

  return {
    _heap: h,
    pop,
    push,
    get size() { return h.length },
    get top() { return h[0] },
  }
}

实现函数

function topK(arr, k) {
  const h = Heap()
  arr.forEach((e) => {
    h.push(e)
    if (h.size > k) h.pop()
  })
  return h.top
}

2. LRU

js 中无论是 object key 还是 map key，都具有后 set 即在最后的特性

function lru(n) {
  const m = new Map
  const limit = () => {
    if (m.size > n)
      m.delete(m.keys().next().value)
  }
  const get = (key) => m.get(key)
  const set = (key, val) => {
    if (m.has(key)) m.delete(key)
    m.set(key, val)
    limit()
  }
  return { get, set }
}