题目描述

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

有一种比较简洁的思路：由于是一个整数区间，所以可以对每一个数进行判断，那么如何判断某个数中1出现了多少次呢？注意到如果一个数一直被10除，如果被10整除后的余数是1，那么一定出现了数字1。举个例子，数字11，被10整除之后的数字是1，说明出现了数字1，除以10后变成了1，发现被10整除之后的余数是1，所以1一共出现了两次。这样就能判断某一个数字1出现的数字了。剩下的工作的循环对每一个数字出现的次数进行统计就可以了。

下面是基于这种思路的实现代码（已被牛客AC）：

package com.rhwayfun.offer;

public class NumbersOf1Between1AndN {

    public int NumberOf1Between1AndN_Solution(int n) {
        if(n == 0) return 0;
        if(n <= 9) return 1;
        int number = 0;
        for (int i = 1; i <= n; i++) {
            number += numbersOf1(i);
        }
        return number;
    }

    private int numbersOf1(int i) {
        int number = 0;
        while(i > 0){
            if(i % 10 == 1) number++;
            i /= 10;
        }
        return number;
    }

    public static void main(String[] args) {
        int N = new NumbersOf1Between1AndN().NumberOf1Between1AndN_Solution(0);
        System.out.println(N);
    }
}