剑指 Offer 43. 1～n整数中1出现的次数

- 日理万妓 2022-11-30 12:46 121阅读 0赞

**在LeetCode上看到了这题一个解法，记录一下**

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
    
     
    
    示例 1：
    
    输入：n = 12
    输出：5
    示例 2：
    
    输入：n = 13
    输出：6
     
    
    限制：
    
    1 <= n < 2^31
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 具体思路 ###

用递归的方法来解决这道题  
给定一个数字，固定最高位，求出该数字能超过10的多少次方的最大值。  
要分最高位是1和不是1来讨论  
**最高位是1**  
如 1234能超过1000即10的三次方，123能超过100即10的二次方。

*  把最高位标为high，10的n次方标为pow。则1234的high为1，pow为1000。
 *  把最高位之后的剩余数字标为last，则1234的last为234
 *  f(n)为求中1的个数的函数，那么`f(1234) = f(pow-1)+f(last)+last+1 = f(999)+f(234)+234+1`
    
     *  首先要算1-999之中的1的个数，即f(999)
     *  再算1000-1234之中1的个数，即f(234)+234+1，实际上分成了两部分去算
        
         *  234+1，算的是千分位上1的个数，即从1000，1001，1002，…1233，1234，这些数千分位总共出现过 235次 1
         *  再算千分位之外的1的个数，即算234中1出现的个数，就是f(234)

**最高位大于1**  
如 3210，最高位high=3，pow=1000，last=210

*  首先还是算1-999之中1的个数，即f(999)
 *  再算1000-1999之中1的个数
    
     *  先算千分位包含1的个数，即1000,1001,1002,…1998,1999这些数字千分位包含1的个数为1000
     *  再算其他位包含1的个数，即f(999)
 *  再算2000-2999之中1的个数，即f(999)
 *  再算3000-3210之中1的个数，即f(210)
 *  总和为 f(999)+1000+f(999)+f(210)
 *  易得公式 pow+f(pow-1)\*high+f(last)

**总结**

f(n):
    	if(high==1)
    		return f(pow-1)+f(last)+last+1
    	else
    		return pow+f(pow-1)*high+f(last)

class Solution { 
        public int countDigitOne(int n) { 
            return f(n);
        }
        
        int f(int n){ 
            if(n<=0){ 
                return 0;
            }
            String str = String.valueOf(n);
            int high = str.charAt(0) - '0';
            int pow = (int)Math.pow(10,str.length()-1);
            int last = n - high*pow;
            if(high == 1){ 
                return f(pow-1)+last+1+f(last);
            }else{ 
                return pow+f(pow-1)*high+f(last);
            }
        }
    }

原答案连接：  
https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/javadi-gui-by-xujunyi/