比如今天的每日一题： https://leetcode.cn/problems/random-pick-with-blacklist/， 还有这些： https://leetcode.cn/tag/randomized/problemset/
毕竟随机结果没法直接对比标准答案，感觉要判断正误就挺麻烦，但 leetcode 可以测出来正确性。
有时候写出来某个细节差个+1 -1 ，那概率分布也差不太多吧，它也能测出来有错误不给 AC 。 感觉就挺神奇的。
没有搜到有对这个的讨论。。
This topic created in 1416 days ago, the information mentioned may be changed or developed.
6 replies 2022-06-26 20:16:43 +08:00
 | 1 stein42 Jun 26, 2022  1 应该是用统计学里的假设检验来验证，这里是离散均匀分布，可以用皮尔森卡方检定。 假设检验本身就可能犯第一类错误（拒绝正确结果）和第二类错误（接受错误结果）。 我试过，轻微改变分布还是能通过。 ``` import bisect import random class Solution: ....def __init__(self, n: int, blacklist: List[int]): ........self.m = n - len(blacklist) ........self.ss = [a - i for i, a in enumerate(sorted(blacklist))] ....def pick(self) -> int: ........r = random.randrange(self.m) ........return r + bisect.bisect_right(self.ss, r) ``` ``` import bisect import random class Solution: ....def __init__(self, n: int, blacklist: List[int]): ........self.m = n - len(blacklist) ........self.ss = [a - i for i, a in enumerate(sorted(blacklist))] ....def pick(self) -> int: ........if random.random() < 1 / (100 * self.m): ............r = 0 ........else: ............r = random.randrange(self.m) ........return r + bisect.bisect_right(self.ss, r) ``` |
 |
 | 3 SingeeKing PRO 咱就说，有没有一种可能，他是跑了你的代码然后检查输入输出 |
| 4 SingeeKing PRO 哦不我看错了，忽略我… |
 | 5 adjusted Jun 26, 2022 1 random 设置下 seed 吧 |
 | 6 wy315700 Jun 26, 2022 via Android special judge 写一段代码来检测你的输出的，写 oj 的时候经常用到的，除了随机数算法，一些涉及浮点数的可能也要用到 |
Select Language