第三十题：整数中1出现的次数

难易度：⭐⭐⭐

题目描述：
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？
为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次
但是对于后面问题他就没辙了
ACMer希望你们帮帮他,并把问题更加普遍化，可以很快的求出任意非负整数区间中1出现的次数
（从1 到 n 中1出现的次数）

本题我的想法是这样的：
例如对数字 21134而言
我将求得从1到21134的过程中，1出现的个数分解成：

1 ~ 20000 中 1 出现的个数
+
1 ~ 1000 中 1 出现的个数
+
1 ~ 100 中 1 出现的个数
+
1 ~ 30 中 1 出现的个数
+
1 ~ 4 中 1 出现的个数

当然这样算得的结果是不正确的，不过对于一个数字按照我的思想逐位进行计算无疑将问题分解成了更简单的问题：

 public static int process(int target){
        if(target == 0){
            return 0;
        }
        int times = 0;
        int res = 0;
        int temp = target;
        while(temp >= 10){
            res += Math.pow(10,times) * (target / Math.pow(10,times + 1));
            times++;
            temp /= 10;
        }
        if(temp!=1){
            res += Math.pow(10,times);
        }else{
            res += 1;
        }
        return res;
    }

上述的方法就是输入一个数字类似于 4，2000，10000 这样 除了个位数 都能整除10的数字，然后返回1 ~ target出现1 的个数的这样一个方法。不过我在牛客网online judge上按照上面的思想并没有通过测试，原因是因为，我忘记了一些东西
数字 21134而言：
1 ~ 21134中出现 1 的个数的统计过程 应该是这样的：

1 ~ 20000 中 1 出现的个数
+
1 ~ 1000 中 1 出现的个数
+
1 ~ 100 中 1 出现的个数 + 100 * 1
+
1 ~ 30 中 1 出现的个数 + 30 * 2
+
1 ~ 4 中 1 出现的个数 + 4 * 2

这个过程只可意会不可言传。希望大家自行理解。因为本题只是一刷，看到牛客后面评论区有很好的代码，二刷的时候会总结，不过今日匆忙，只能草草了事。最后附上屎一样的代码：

public class Solution {

    public int NumberOf1Between1AndN_Solution(int n) {
        if(n <= 0){
            return 0;
        }
        int res = 0;
        int digit = 1;
        int temp = n;
        while(temp >= 10){
            temp /= 10;
            digit++;
        }
        
        int curRes = 0;
        int times = 0;
        while(digit > 0){
            if(isOne(getDigitNum(n,digit))){
                curRes = process(getMyNum(n,digit),times);
                res += curRes;
                times++;
                digit--;
            }else{
                curRes = process(getMyNum(n,digit),times);
                res += curRes;
                digit--;
            }
        }
        return res;
    }
    public static int getDigitNum(int num,int digit){
        return (num / (int)Math.pow(10,digit - 1)) % 10;
    }
    
    public static int getMyNum(int num,int digit){
        int temp = (num / (int)Math.pow(10,digit - 1)) % 10;
        return temp * (int)Math.pow(10,digit - 1);
    }

    public static boolean isOne(int num){
        return num == 1;
    }

    public static int process(int target,int t){
        if(target == 0){
            return 0;
        }
        int times = 0;
        int res = 0;
        int temp = target;
        while(temp >= 10){
            res += Math.pow(10,times) * (target / Math.pow(10,times + 1));
            times++;
            temp /= 10;
        }
        if(temp!=1){
            res += Math.pow(10,times);
        }else{
            res += 1;
        }
        return res + target * (int)Math.pow(2,t - 1);
    }
}