1. 题目描述

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

2. 题目分析

1. 最常见做法和想到的就是从1~n依次遍历，然后遍历每一个数字的每一位数，判断其是不是等于1，累加return
2. 这是介绍一种新的解法，类似找规律的样子

)

3. 题目代码

public static int NumberOf1Between1AndN_Solution(int n) {
        int sum = 0;
        int hight = n / 10;
        int low = 0;
        int cur = n % 10;
        int dight = 1;
        // 4356
        while (hight != 0 || cur != 0) {
            if (cur == 0) {
                sum += dight * hight;
            } else if (cur == 1) {
                sum += dight * hight + low + 1;
            } else if (cur >= 2) {
                sum = sum + dight * (hight + 1);
            }
            low = low + cur * dight;
            cur = hight % 10; // 5
            dight = dight * 10; // 10
            hight = hight / 10; // 43
        }
        return sum;
    }