给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例:
输入: 13
输出: 6
解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。
递归解决。分为首位为1和首位不为1两种情况：
1.首位为1，如12345。
先考虑大于等于10000的：则10000~12345的首位1共贡献2346个，另外0到2345贡献的后4位的1的总数递归解决：f(2345)。
再考虑小于10000的：递归解决：f(9999)
2.首位不为1，如23456。
首位的1贡献10000个（10000~19999）。然后后面4位：再分为，1：大于等于20000的：0~3456，f(3456)个。2：小于20000的：0~9999 和 10000到19999，一共2*f(9999)
1 class Solution { 2 public: 3 int countDigitOne(int n) { 4 if(n<1){return 0;} 5 string s=to_string(n); 6 int high=s[0]-‘0‘; 7 int p=int(pow(10,s.size()-1)); 8 s.erase(0,1); 9 int low=atoi(s.c_str()); 10 if(high==1){ 11 return (low+1)+countDigitOne(low)+countDigitOne(p-1); 12 } 13 else{//high>1 14 return p+high*countDigitOne(p-1)+countDigitOne(low); 15 } 16 } 17 };
原文：https://www.cnblogs.com/FdWzy/p/12353967.html