题目重点:从混合标签袋入手,用全部标签都错误的约束推断纯金币、纯银币与混合袋。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 标为混合的袋子不可能真混合,因为每个标签都贴错;纯金袋只含金币、纯银袋只含银币,混合袋至少两种币都有。
- 只抽一次,抽取过程不改变袋子的类别;三个真实类别各恰好对应一个袋子。
解题路线
- 唯一有保证的信息入口是标为混合的袋子:它真实必为纯金或纯银,所以抽出的币直接确定整袋真实类别。
- 若抽到金币,该袋是真金;剩余标签金与银的袋子中,标金的不能真金,而真金已用,因此标金袋只能真混合,标银袋真银。
- 若抽到银币,对称地标混合袋真银;标银袋不能真银且真银已用,因此标银袋真混合,标金袋真金。
- 从标金或标银袋取币不保证成功,因为这些袋子可能是混合袋,抽到单枚不能总是区分其真实类别。
手动走一遍
标记 [金,银,混合] 的三个袋子,抽标混合袋得到银币,则真实类别依次为 [金,混合,银];检查三袋标签均与真实类别不同。
规模与取舍
只做一次抽样和常数次逻辑推导,时间 O(1)、额外空间 O(1);关键不是计算量,而是选择能让单次观察具有确定性的袋子。
易错点与追问
容易失分的边界
- 从标金袋抽到金就认定它为纯金,违反标签全错前提。
- 认为标混合袋仍有概率混合,忽略所有标签均错误。
- 只推断抽样袋的类别,不检查剩余两袋唯一对应关系。
继续深挖
- 若只保证恰有两个标签错误,单次抽样是否仍足够?
- 若混合袋的抽样可被对抗性选择,为什么本方案仍有效?
