【剑指offer-Java版】32从1到n的整数中1出现的次数

我会带着你远行 2022-08-21 09:48 102阅读 0赞

1到n中1出现的次数：  
书上的讲解实在是没看懂，翻翻作者的博客找到了一个通俗解法，自己又补充了一些思考细节，全在注释里面了

public class _Q32<T> {
    
        public static void main(String[] args) {
    
            /* 5 6 16 20 */
            System.out.println(NumberOf1(12));
            System.out.println(NumberOf1(13));
            System.out.println(NumberOf1(55));
            System.out.println(NumberOf1(99));
        }
    
        /**
         * @comment 思路：
         * 书中的例子并没有看懂，所以查找了作者的博客，博客中有关于该问题的通俗解法，时间复杂度为O(logn)
         * 
         * 作者的博客地址： http://zhedahht.blog.163.com/blog/static/25411174200732494452636/
         * 
         * 该思路的举例分析：
         * 我是按照各位做统计的，某位左侧代表这个循环体出现了几次，右侧代表这个体中1出现了多少遍，如:
         * 30143:
         * 由于3>1,则个位上出现1的次数为(3014+1)*1  -- 当个位为1的时候，可以有 1 11 21 ... 30141这么多种
         * 由于4>1,则十位上出现1的次数为(301+1)*10  -- 当十位为1的时候，可以有 10 11 12 .. 19 110 111 ...119 ... 29119 ... 30113
         * 由于1=1，则百位上出现1次数为(30+0)*100+(43+1) -- 当百位为1的时候，可以有 100 101 .. 199 1100...29199 ... 30143
         * 由于0<1，则千位上出现1次数为(3+0)*1000 -- 千位为0那么只能是 1000 1001 ... 1999 11000 11001 ... 11999 ... 21999
         *
         *  注:以百位为例，百位出现1为100~199，*100的意思为单步出现了100~199，100次，*30是因为出现了30次100~199,
         *  +(43+1)是因为最后一次301**不完整导致
         *  
         * 那么有些同学可能会觉得这样会不会出现重复统计的情况，比如针对上述的例子，如果取 11111岂不是会被计算5次
         * 其实题目的意思是求1出现的次数，也就是不管这个数是多少位的，比如11这个数1出现次数是2
         * 而上述的算法计算的时候就是针对每一位进行统计的，所以不存在重复计数的问题
         * 
         * 有了这样的思路之后，剩下的就是抽象出可以进行编码的表达式，如下：
         * 假设当前考虑的位是第k位(从右向左，从0计数),原数为n
         * 那么如果当前第k位为0     ：(n/pow(10, k+1) + 0)*pow(10, k)
         * 那么如果当前第k位为1     ：(n/pow(10, k+1) + 0)*pow(10, k) + (n%pow(10, k) + 1)
         * 那么如果当前第k位大于1 ：(n/pow(10, k+1) + 1)*pow(10, k) 
         * 依次对n的每一位进行计算并累加，时间复杂度是O(logn)
         * 
         * 此处暂时就没有考虑大数问题 -- 需要的时候直接改为long或者BigInteger就好了
         * 
         * @param n
         * @return   
         * @return int  
         * @throws
         * @date 2016年4月16日 下午8:36:48
         */
        public static int NumberOf1(int n){
            if(n <= 0) return 0;
    
            int result = 0;
            int nn = n;
            int k = 0;
            int cur = 0;
    
            while(nn > 0){
                cur = nn % 10;
                nn = nn / 10;
    
                switch (cur) {
                case 0: // == 0
                    result += n / (int) Math.pow(10, k + 1) * (int) Math.pow(10, k);
                    break;
                case 1: // == 1
                    result += n / (int) Math.pow(10, k + 1) * (int) Math.pow(10, k) + (n % (int) Math.pow(10, k) + 1);
                    break;
                default: // > 1
                    result += (n / (int) Math.pow(10, k + 1) + 1) * (int) Math.pow(10, k);
                    break;
                }
    
                k++;
            }
    
            return result;
        }
        }