整数中1出现的次数（从1到n整数中1出现的次数）

1、最高位：为1----则是后面位（如123，则应取23）；不为1------则是最高位的（如223，则取100）

2、其它位：如223，可分为0-23,24-123,124-223。其它位是指24-123,124-223的除最高位的1其余可能有的1，可以发现24-123其实其它位为：25,26···99,0,1,2···23,可计算为：最高位*后一位的权重*除最高位其余位数（2*2*10，可看做每一位为1时，其它位为任意整数的所有可能）

3、再加上0-23.

class Solution {
public:
    string intostr(int n)
        {
        string s;
        while(n!=0)
            {
            s+=n%10+'0';
            n=n/10;
        }
        string res;
        for(int i=s.size()-1;i>=0;i--)
            {
            res+=s[i];
        }
        return res;
    }
    int pow(int len)
        {
        int sum=1;
        while(len>0)
        {
            sum*=10;
            len--;
        }
        return sum;
    }
    int sumall(string s,int len)
        {
        if(len==s.size()-1)
            {
            if((s[len]-'0')!=0)
                return 1;
            else return 0;
        }
        int first=0,second=0,last=s[len]-'0';
        if(last>1)
            first=pow(s.size()-len-1);
        else if(last==1)
             first=atoi(&s[0]+len+1)+1;
            second=last*(s.size()-len-1)*pow(s.size()-len-2);
            return first+second+sumall(s,len+1);
    }
    int NumberOf1Between1AndN_Solution(int n)
    {
      if(n<=0)
          return 0;
        string s;
        s=intostr(n);
        int sum=0;
        sum=sumall(s,0);
        return sum;
    }
};