题目描述

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

解题思路

对于某个数k（0<=k<=9），在个位出现1次，十位出现10次，百位出现100次。

对于1到n，中k的个数有如下规律：

某一位大于k = 1，只看高位，如103，那么当前位为各位时，3>1,只看高位，个位为1的数有（高位数+1）× 1（12+1）× 1，十位则乘以10。

某一位等于k = 1，参考高位和低位，如103，百位，为1==1，高位为0，低位为03，那么百位为1的个数为（高位）× 100 + 低位 + 1，（0 × 100）+ 03 + 1 = 4

某一位小于k = 1，参考高位，如103，十位为0<1，那么十位的1的个数为 高位 × 10，1 × 10 = 10。

实现

public class Solution {    public int NumberOf1Between1AndN_Solution(int n) {        if (n <= 0) return 0;        int r = 1;        int high = n;        int count = 0;        while (high > 0){            int cur = n % (r * 10) / r;            high = n / (r * 10);            int low = n % r;            if (cur > 1) count += (high+1) * r;            else if (cur == 1) {                count += high * r + low + 1;            }            else count += high * r;            r *= 10;        }        return count;    }}