从1到n之间的数字1出现的次数
例如N=11时结果为4（只有1,10,11含1）
1.常规方法（暴力）时间复杂度O（n*logn）当n很大的时候，效率低。
#include <iostream>#include <cstdio>using namespace std;int function (int n){int count=0;for (int i=1 ;i<=n;i++){int j = i;while (j){if (j%10==1)count++;j/=10;}}return count;}int main (){int n;while (scanf ("%d",&n)!=EOF){printf ("%d\n", function(n));}return 0;}
2.编程之美上解法（时间复杂度O（logn））
#include <iostream>#include <cstdio>using namespace std;int function (int n)//按照每一位出现1的次数来进行计算{int factor =1 ;//factor 是该位的权值int res = 0;int low, cur, high;while (n / factor){low = n % factor;//数字的低位cur = n / factor % 10;//数字当前位置的数high = n / factor / 10;//数字的最高位if (cur==0)res += high * factor;else if(cur==1)res += high * factor + low + 1;else res += (high + 1) * factor;factor *= 10;}return res;}int main(){int n;while (scanf("%d",&n)!=EOF){printf("%d\n",function(n));}return 0;}