tiktok卷王MLE OA, 直接气急败坏关掉窗口。

beijianzhizun 发表于 2020-11-24 02:49
第二题不就是拿K次攻击的能赢的组合除以所有k次攻击的可能造成的看血量来算。
我写了个方程：

Make sense， 我也是用类似的方法做的，但是时间复杂度太高了。题目里面说尝试用close math form，简直有毒

匿名者 发表于 2020-11-24 01:10
既相当于投骰子，骰子有从0到m个数字面，投k次，问你出现的数字之和是否能大于等于n。当k比较大的时候这道 ...

所以，求教k比较大的时候该怎么做才能保证误差范围？

我的思路是 第二题其实用dp就可以应对大部分的情况，时间复杂度大概是O(n * m * k)。无法用dp解决的是n, m, k都很大的时候，这种情况下其实ituitively就可以觉得概率是1，比如test case 3给的就是n, m, k都是1000的情况。这种情况下其实可以用中心极限定理去近似，如果n小于均值减去5倍标准差就可以认为概率是1。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

chunlun2 发表于 2020-11-23 17:35
我這邊的 hasCircle 是如果從d開始檢查的話 由於dfs沒法回到d這個點 (d->a->b->c->a->迴圈) 則不算有circ ...

但是从a开始检查的话会回到a的，请问大神怎么解决呀

去年我做腾讯OA也是两小时4道题，只做出了1.5道……然后还是收到电面了。所以没关系的

匿名者 发表于 2020-11-23 16:53
我的思路是 第二题其实用dp就可以应对大部分的情况，时间复杂度大概是O(n * m * k)。无法用dp解决的是n, m, ...

兄弟能说说dp的思路吗？谢谢！

楼主太可爱了，昨天承包我的笑点一整天

deepli 发表于 2020-11-24 06:40
兄弟能说说dp的思路吗？谢谢！

1. dp = [1.0] + [0.0] * (N - 1)
   
2. for _ in range(K):
   
3.     newdp = [0] * N
   
4.     for i in range(len(dp)):
   
5.         if dp[i] > 0:
   
6.             for j in range(M + 1):
   
7.                 if i + j < N:
   
8.                     newdp[i + j] += dp[i] / (M + 1)
   
9.     dp = newdp
   
10. return 1 - sum(dp)

复制代码

[/i][/i]