递归+string

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        if(n<=0) return 0;
        string str=to_string(n);

        return NumberOf1(str,0);
    }
    int NumberOf1(string& str,int startIndex){
        if(str.empty() ||str[startIndex]<'0'||str[startIndex]>'9'||str[startIndex]=='\0') return 0;

        unsigned int length=str.size()-startIndex;

        int first=str[startIndex]-'0';
        if(length==1 && first==0)
            return 0;
        if(length==1 && first>0)
            return 1;

        int numFirstDigit=0;
        if(first==1){
            string subStr=str.substr(startIndex+1);
            numFirstDigit=atoi(subStr.c_str())+1;
        }
        else if(first>1)
            numFirstDigit=PowerOf10(length-1);

        int numOtherDifit=first*(length-1)*PowerOf10(length-2);

        int numRecursive=NumberOf1(str, startIndex+1);

        return numFirstDigit+numOtherDifit+numRecursive;
    }
    int PowerOf10(unsigned int n){
        int result=1;
        for(unsigned int i=0; i<n; i++)
            result = 10*result;

        return result;
    }

};