找最小正整数M使N乘M只由0和1组成
哪些公司问过
答案要点
- 转化为找N的最小0/1倍数X,M=X/N
- 按余数做BFS:r→(10r)%N和(10r+1)%N,起点为1
- 先扩展添0分支,首次到达余数0即为最小X
- 记录前驱回溯构造X,再做大数除法得到M
- 余数最多N个状态,时间空间O(N);抽屉原理保证有解
易错点
- 直接枚举M并用整数相乘,溢出或超时
- BFS存实际数值而不是余数,状态爆炸
- 扩展顺序先1后0,得到的不是最小值
面试官常见追问
- 为什么一定有解?
- 为什么不能直接枚举M?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。