birthday problem

birthday problem

生日问题是指在随机选择的一群人当中有两人的生日相同的概率。如果一个房间里有23个或23个以上的人，那么至少有两个人的生日相同的概率要大于50%；对于60或者更多的人，这种概率要大于99%。

该问题的计算公式就是 从365个元素中取出n个元素的排列 除以 365的n次方

通用计算方式如下，即计算拥有all个数量属性取值的个体count 个时，出现属性值相同的概率，这里考虑到值会比较大，所以使用BigInt

1
2
3
4
5
6
7
8
9
10
11
12
13
const calc = (count, all) => {
  let c = count
  let result = 1n
  while (c > 0n) {
    c -= 1n
    result *= (all - c)
  }
  return `${Number(1000n - result * 1000n / (all ** count)) / 10}%`
}
calc(23n, 365n) // "50.8%"
calc(60n, 365n) // "99.5%"

Algorithm

Shortest subarray with sum at least k

在LeetCode刷算法题，记录一下一道比较难的题目和至少为 K 的最短子数组

问题描述

返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。

如果没有和至少为 K 的非空子数组，返回 -1 。

其中：

  • 1 <= A.length <= 50000
  • -10 ^ 5 <= A[i] <= 10 ^ 5
  • 1 <= K <= 10 ^ 9

最先想到的是依照数值长度进行遍历，但时间复杂度为O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[]} A
 * @param {number} K
 * @return {number}
 */
const shortestSubarray = (A, K) => {
  let preSum = 0
  let count = 1
  while (count <= A.length) {
    preSum += A[count - 1]
    let sum = preSum
    if (sum >= K) return count
    for (let i = 1; i + count <= A.length; i ++) {
      sum = sum - A[i - 1] + A[i + count - 1]
      if (sum >= K) return count
    }
    count += 1
  }
  return -1
}

之后参考了网上的资料，可以使用Sliding Window的方法，复杂度可以下降到O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number[]} A
 * @param {number} K
 * @return {number}
 */
const shortestSubarray = (A, K) => {
  if (!A.length) return -1
  let S = [0]
  for (let i = 0; i < A.length; i++) {
    S[i + 1] = S[i] + A[i]
  }
  const queue = []
  let ans = A.length + 1
  for (let j = 0; j < A.length + 1; j++) { 
    while (queue.length && S[j] <= S[queue[queue.length - 1]]) {
      queue.pop()
    }
    while(queue.length && S[j] >= S[queue[0]] + K) {
      ans = Math.min(ans, j - queue.shift())
    }
    queue.push(j)
  }
  return ans < A.length + 1 ? ans : -1
}
Algorithm