核心思想
个位、十位、百位…… 每一位分开算:单独算「在这一位上 2 一共出现多少次」,全部累加。
把数字拆成三部分:
* base:当前位的基数,个位base=1,十位base=10,百位base=100
* high:当前位左边高位
* cur:当前位本身的数字
* low:当前位右边低位
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三种分支规则(针对统计数字 2)
1. cur < 2:当前位数字比 2 小
> 这一位出现 2 的次数:high * base
2. cur == 2:当前位正好等于 2
> 这一位出现 2 的次数:high * base + low + 1
3. cur > 2:当前位数字比 2 大
> 这一位出现 2 的次数:(high + 1) * base
> 不断 base *=10,从个位一直处理到最高位,把每一位的结果累加就是答案。
通俗理解每一种情况
举例子,统计十位上 2 出现多少次:
1. cur<2:比如 517,十位是 1。十位上 2 只能来自 0~4 循环,每轮 10 次,high*base。
2. cur=2:比如 527。完整轮次high*base,再加上 0~low(0‑7)一共 low+1 个。
3. cur>2:比如 537。可以取到 0‑5 全部轮次,所以(high+1)*base。
> 注意点:
1.要用long long,防止溢出!t 很大时 int 会爆。本题不用
2.base 会不断 ×10,循环条件base <= t。
3.num的取值范围是{1,2,3,4,5,6,7,8,9}num=0时代码有改动不能用,嘻嘻
最后再说一下本方法的复杂度:O(log n)
点个赞吧