思路：假设数字为21345，用strN字符串来存储。
把数字分为2段，一段是1~1345，另一段是1346~21345.
（1）1345~21345中，万位上出现1的数字在10000~19999中，有10^4个。如果n的长度为length，则共有10^(length-1)次。
（2）如果首位数字等于1，比如从10000~12345，则最高位出现1的次数为2345+1=2346次，即共有atoi(strN+1)+1次。
（3）除了第一位的数之外，其他位上有1的次数：再把1346~21345分成2段，1346~11346,11236~21346，每一段中除去其中的一个数为1之外，其他的每位均可以取0~9，所以有2*10^3次。即共有first*10^(length-2)次。
（4）1~1345中1的次数，就是21345中除去首位之后的次数。迭代求得。
int NumberOf1(const char* strN); int PowerBase10(unsigned int n); int NumberOf1Between1AndN(int n) { if(n<=0) return 0; char strN[50]; sprintf(strN,"%d",n); //整数转为字符串 return NumberOf1(strN); } int NumberOf1(const char* strN) { if(!strN||*strN<'0'||*strN>'9'||*strN==' ') return 0; int first=*strN-'0'; unsigned int length=static_cast<unsigned int>(strlen(strN)); //strlen(strN)求字符串的长度，除去“ “。static_cast<unsigned int>转为无符号整型 if(length==1&&first==0) return 0; if(length==1&&first>0) return 1; //假设strN是'21345' //numFirstDigit是数字10000~19999的第一个位中的数目 int numFirstDigit=0; if(first>1) numFirstDigit=PowerBase10(length-1); else if(first==1) numFirstDigit=atoi(strN+1)+1; //atoi字符串转换为整型。atoi(strN+1)是把除高位外的字符串转化为整数。10000~12345中最高位出现1个次数为除去最高数字滞后于剩下的数字再加1. //numOtherDigits是1346~21345中除了第一位之外的数位中的数目 int numOtherDigits=first*(length-1)*PowerBase10(length-2); //numRecursive是1~1345中的数目 int numRecursive=NumberOf1(strN+1); return numFirstDigit+numOtherDigits+numRecursive; } int PowerBase10(unsigned int n) //从10000~99999的5位数中最高位为1，一共出现了10^4个 { int result=1; for(unsigned int i=0;i<n;++i) { result *=10; } return result; }