返回列表

LeetCode 1230. Toss Strange Coins 抛硬币

默认分类 2020/07/02 12:21

题目描述

有一些不规则的硬币。在这些硬币中,prob[i] 表示第 i 枚硬币正面朝上的概率。

请对每一枚硬币抛掷 一次,然后返回正面朝上的硬币数等于 target 的概率。

样例

输入:prob = [0.4], target = 1
输出:0.40000

输入:prob = [0.5,0.5,0.5,0.5,0.5], target = 0
输出:0.03125

限制

1 <= prob.length <= 1000
0 <= prob[i] <= 1
0 <= target <= prob.length

如果答案与标准答案的误差在 10^-5 内,则被视为正确答案。

代码如下:

function fn(p, n) {
  n = n === 0 ? p.length : n
  n = n === 1 ? p.length - 1 : n
  // p = [0.1, 0.5, 0.9]
  // n = 1
  // 方法一:直接模拟10万次,每次抛p.length个硬币,有n个朝上
  let count = 100000
  let result = 0
  for (let i = count; i > 0; i--) {
    let up = 0
    p.forEach(it => {
      if (it === 1) up++
      else if (Math.random() <= it) up++
    })
    if (up === n) result++ 
  }
  console.log(result / count)
  // 方法二:找出抛p.length个硬币,有n个朝上的组合,然后求和
  var way = combine(p, n)
  let hh = 0
  way.forEach(it => {
    let dd = 1
    p.forEach(q => {
      dd *= (it.includes(q) ? q : 1 - q)
    })
    hh += dd
  })
  console.log(hh)
  // 方法三:动态规划,状态转义
  let len = p.length
  let dp = [1].concat(p).map(() => Array(n + 2).join(',').split('').map(() => 0))
  dp[0][0] = 1
  dp[0][-1] = 0
  // i=0时,j从0到n, dp[0][j] = 0
  for (let i = 1; i <= len; i++) {
    for (let j = 0, max = Math.min(i, n); j <= max; j++) {
      // 状态转移方程
      dp[i][j] = dp[i-1][j-1] * p[i-1] + dp[i-1][j] * (1 - p[i-1])
    }
  }
  console.log(dp[len][n])
}
function combine (list, num) {
  let arr = arrange (list, num)
  let maps = {}
  let result = []
  arr.forEach(it => {
    it.sort()
    if (!maps[JSON.stringify(it)]) {
      maps[JSON.stringify(it)] = true
      result.push(it)
    }
  })
  return result
}
function arrange (list, num) {
  if (num === 1) return list.map(it => [it])
  else if (num < 1 || num > list.length) return []
  // list = [1, 5, 3]
  let result = []
  let len1 = list.length
  for (let i = 0; i < len1; i++) {
    let cur = list[i]
    let left = [].concat(list)
    left.splice(i, 1)
    let arr = arrange(left, num - 1)
    for (let j = 0, len2 = arr.length; j < len2; j++) {
      result.push([cur].concat(arr[j]))
    }
  }
  return result
}


>> 留言评论