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

标签: 剑指Offer  算法  leetcode

LeetCode:剑指 Offer 43. 1~n整数中1出现的次数

在这里插入图片描述


数位 dp



public class Offer43 {

    /**
     *  n = 345 [y] xx
     *
     *  000    00
     *  001    01
     *  ...   ...
     *  344    99
     *
     *
     *  345  * 100
     *
     * @param n
     * @return
     */
    public int countDigitOne(int n) {
        // 临界
        if(n < 0){ return 0; }
        String num = String.valueOf(n);
        // 位数
        int len = num.length();
        // 结果的数量
        int count = 0;

        for (int i = 1; i <= len ; i++) {
            // 取出当前数的前面几个数
            int pre = n / (int)Math.pow(10, i);
            count += pre *(int)Math.pow(10, i- 1);

            // 取出当前位数
            int msb = num.charAt(len - i) - '0';

            // 当前面的为最大值固定时
            if(msb > 1){
                // 当前位数大于 1, 低位的随便取
                count += (int)Math.pow(10, i - 1);
            } else if(msb == 1){
                // 00 到 78
                // 实际有 79 个数
                count += n % (int)Math.pow(10, i - 1) + 1;
            }

        }
        return count;
    }


    public static void main(String[] args) {
        Offer43 o = new Offer43();
        int i = o.countDigitOne(12);
        System.out.println(i);
    }

}

版权声明:本文为qq_43765535原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_43765535/article/details/108597270