给定N，让我们求[1, N]这个区间里的所有数出现了几次1。这道题我们按每一位每一位统计，个十百千万按顺序求即可。比如对于310：
- 我们首先统计个位，首先个位至少出现了1 * 31次，[1, 11, 21... 301]，对于311，因为其只到310，所以我们不需要统计这一个。所以个位总共出现了31次1。
- 十位同理，至少有10 * 3次，[10-19, 110-119, 210-219]，对于31x，因为最大值只到310，所以只有1个。总共十位出现了30 + 1 = 31次1。
- 对于百位，出现了100 * 1次，也就是[100-199]。总共百位出现了100次。
- 所以总共1出现了31 + 31 + 100 = 162次。
我们按照这个思路统计即可，假设输入数字大小为n，时间复杂度O(log10(n))，常数空间，代码如下：
No comments:
Post a Comment