43. 1~n整数中1出现的次数

面试题43. 1~n整数中1出现的次数

输入一个整数 n ,求1~n这n个整数的十进制表示中1出现的次数。

例如,输入12,1~12这些整数中包含1 的数字有1、10、11和12,1一共出现了5次。

 

示例 1:

输入:n = 12
输出:5

示例 2:

输入:n = 13
输出:6

 

限制:

  • 1 <= n < 2^31
class Solution {
    public int countDigitOne(int n) {
        return f(n);
    }
    
    private int f(int n){
        if(n <= 0) return 0;
        String s = String.valueOf(n);
        int h = s.charAt(0) - '0';
        //s.legnth() - 1
        int pow = (int)Math.pow(10,s.length() - 1);
        int last = n - pow * h;
        if(h == 1){
            return f(pow - 1) + last + 1 + f(last);
        }else{
            return h * f(pow - 1) + f(last) + pow;
        }
    }
}

 

上一篇:43.左旋转字符串


下一篇:43.操作标签属性