描述

输入一个整数 n ，求1～n这n个整数的十 进制 表示中1出现的次数

例如，1~13中包含1的数字有1、10、11、12、13因此共出现6次

示例1

输入：13

返回值：6

第一种解法，最简单的暴力方式，遍历每一个数字，判断是否包含1，不过多解释，代码如下

 public int firstNumberOf1Between1AndN_Solution(int n) {
        int result = 0;
        if(n < 1){
            return result;
        }
        for (int i = 1; i <= n; i++) {
             String str =  String.valueOf(i);
            char[] chars = str.toCharArray();
            for (char c : chars) {
                if(c == '1'){
                    result++;
                }
            }
        }
        return result;
    }  

第二种解法，这种方法非常的有意思，需要先理解清楚，才好写代码，将 1 ~ n 的个位、十位、百位、…的 1 出现次数相加，即为 1出现的总次数。假设一个n位数num，规定num的第i为ni,那我们就可以将num写为nx nx-1..n2n1。我们把当前ni规定为cur,低于当前位的数字记为low,高于当前位的数字记为high,10的i次方为10i 记为dight，举个例子我们以3105为例，某一位中出现1的次数，根据cur值的不同，可以分为以下三种情况，

有了以上逻辑，代码如下

 public int secondNumberOf1Between1AndN_Solution(int n) {
        int result = 0;
        if(n < 1){
            return result;
        }
        //i是位数
        for (int i = 1; i <= n; i*=10) {
            int high = n /(i*10);
            int low = n % i;
            int cur = (n/i) % 10;
            if(cur == 0){
                result += high*i;
            }else if(cur == 1){
                result += high*i + (low + 1);
            }else {
                result += (high + 1) * i;
            }
        }
        return result;
    }