问题描述
给定一个十进制整数N,求出从1到N的所有整数中出现”1”的个数。
例如:N=2时 1,2出现了1个 “1” 。
N=12时 1,2,3,4,5,6,7,8,9,10,11,12。...方法一 暴力求解
最直接的方法就是从1开始遍历到N,将其中每一个数中含有“1”的个数加起来,就得到了问题的解。...,ans);
21 }
22 return 0;
23 }
该算法的时间复杂度为O(N*lgN)
(注:此方法对较大的数据有可能会TL)
解法二
1位数的情况:
在解法二中已经分析过...由此我们发现,个位数出现1的次数不仅和个位数有关,和十位数也有关,如果个位数大于等于1,则个位数出现1的次数为十位数的数字加1;如果个位数为0,个位数出现1的次数等于十位数数字。...= 0) {
20 current = (n / i) % 10;
21 before = n / (i * 10);
22 after = n - (n