原题如下：
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。 示例:
输入: 13 输出: 6 解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。
解法1 剑指offer中给出复杂度为O(logn)的解法思路为 例如：给定21345，将其分成两部分1-1345与1346-21345； 其中1346-21345部分的1的个数=最高位中1的个数+除最高位外1的个数 那么最高位中1的个数
最高位大于1最高位等于110^（位数-1）该数-10^（位数-1）+1除最高位外的1的个数=最高位数字*（位数-1）*10^（位数-1）； 其中1-1345部分使用递归，书中将数字装换为字符，利用指针移位，本代码直接利用数字进行计算：
class Solution { public: int countDigitOne(int n) { if(n<=0) return 0; if(n>0&&n<10) return 1; return num(n); } int num(int n){ int first=n,p=0,sum1=0,sum2=0,sum3=1; for(int i=1;i<=n;i*=10){ if(first<10) break; first=n/i; p++; if(i==1000000000) break; } if(p==0&&first>0) return 1; if(p==0&&first==0) return 0; sum2=first*(p-1)*power(p-2); if(first>1) sum1=power(p-1); else if(first==1) sum1=n-first*power(p-1)+1; sum3=num(n-first*power(p-1)); return sum3+sum1+sum2; } int power(int q){ int result=1; for(int i=0;i<q;++i) { result*=10; if(result==1000000000) break; } return result; } };执行用时 : 4 ms, 在Number of Digit One的C++提交中击败了96.68% 的用户 内存消耗 : 8.3 MB, 在Number of Digit One的C++提交中击败了21.57% 的用户
解法2 被评论区大神闪了一下腰，短短几行就搞定； a=n/i,b=n%i; 当a的个位大于1时，百位为1的数总共出现了(a/10+1)*i次 当a为1的时候，百位为1的数总共出现了(a/10)*i+(b+1); 当a为0的时候，百位为1的数出现了(a/10)*i次； 因此可以根据a的个位是否为1分成2中情况计算；9=>a个位>=2时(a/10+1)和0=<a个位<=1时（a/10）表达式与（a+8）/10相同,可以写出以下代码：
class Solution { public: int countDigitOne(int n) { int cnt=0; for(long int i=1;i<=n;i*=10){ int a=n/i,b=n%i; cnt+=(a+8)/10*i+(a%10==1)*(b+1); if(i==1000000000) break; } return cnt; } };执行用时 : 4 ms, 在Number of Digit One的C++提交中击败了96.68% 的用户 内存消耗 : 8.3 MB, 在Number of Digit One的C++提交中击败了11.76% 的用户
