1 到 n 中数字 2 出现的总次数
哪些公司问过
中国民生银行信用卡中心1
答案要点
- 按位统计:对每一位求数字 2 在该位出现的次数再求和
- 拆分 high = n/(10p)、cur = (n/p)%10、low = n%p
- cur<2:high×p;cur=2:high×p+low+1;cur>2:(high+1)×p
- 复杂度 O(log n),多组数据循环读到 −1
- 数字 2 无需处理前导零;p 和结果用 64 位整数
易错点
- 逐个数统计,n 到 10^9 以上会超时
- cur 等于 2 时漏掉 low + 1 这部分
- 迁移到数字 0 时忘了处理前导零
面试官常见追问
- 如果统计的是数字 0 呢?
- 数位 DP 怎么做?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。