题解 | #整数中1出现的次数（从1到n整数中1出现的次数）#

题目：整数中1出现的次数（从1到n整数中1出现的次数）

描述：输入一个整数n，求1～n这n个整数的十进制表示中1出现的次数
例如，1~13中包含1的数字有1、10、11、12、13因此共出现6次

示例1输入：13返回值：6

解法一解题思路：在暴力法中，可以设定一个指针变量去监测当前位置，将当前位置的值不断进行取余，取整，以此来计算该数中1的个数，最后将1的个数值相加，取得最终结果值。

举例进行分析：当输入的n的值为13时，所有的数分别为1~13，循环1~13所有的数字，其中出现1数字的数字有1、10、11、12、13，将里面1的数字逐个相加，最终得到返回值，具体分析如下表所示：

其java代码如下所示：

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int num = 0;
        for(int i = 1;i <= n;i++){//逐个遍历
            num += sum1(i);
        }
        return num;
    }
    public int sum1(int i){//判断一个数字是否满足有1的存在
        int count = 0;
        while(i != 0){
            if(i % 10 == 1)
                count++;
            i = i / 10;
        }
        return count;
    }
}

其时间复杂度为O(N)。

解法二思路分析：因为包含1数字的数字个数只有那么几种，所以也可以采用归纳总结的方法去判断，首先我们判断个位上的数字，在个位上，1的数量会随着间隔10出现一次，如果我们以10为一个循环的话，在每一个完整的循环里边都应该存在1个1，例如数字24，每隔10为一个循环的话，可以分为两个完整的循环，分别是0~9，10~19，但是19以后会有一个不完整的循环，所以我们需要在这个不完整的循环当中去判断1的数量，当不完整的循环中只有一个数字的时候，即只有20时，是没有1的存在的，当不完整循环中的数字数量大于1的时候，则1的数量就会出现，所以我们总结归纳，在个位上1的数量为n/10+（n%10！=0？1：0）。

int shi = n%100;
int count = 0;
if(k > 19)
    count = (n/100) * 10 + 10;
else if(k < 10)
    count = (n/100) * 10;
else
    count = (n/100) * 10 + (shi - 10 + 1);

以下我们就不进行分析，直接进行归纳总结：

下面我们进行实例分析：

import java.util.*;
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        if(n <= 0)
            return 0;
        int count = 0;
        for(int i = 1;i <= n;i *= 10){
            long div = i * 10;
            count += (n / div) * i + Math.min(Math.max(n % div - i + 1,0),i);
        }
        return count;
    }
}